Seminar for Mathematical Logic

PROGRAM

Plan rada Seminara za logiku za MAJ 2018.

Seminar za matematicku logiku Matematickog instituta SANU nastavlja rad u letnjem semestru 2011/2012.g. na ovoj adresi: Kneza Mihaila 36/III sprat, soba 301f - sala za seminare. Cetvrtkom posle podne, ali od 15:00 sati, odrzavace se predavanja na Seminaru iz verovatnosnih logika pod rukovodstvom Profesora Miodraga Raskovica koji je u decembru 2007. dobio akreditaciju Naucnog veca Instituta. Na taj nacin, ponovo, kao pre vise decenija, postoje dva logicka seminara.

PETAK, 11.05.2018. U 14:15, Matematicki institut SANU, sala 301f
Petar Markovic, PMF Novi Sad
HIPOTEZA O DIHOTOMIJI PROBLEMA ZADOVOLJENJA USLOVA JE (VEROVATNO) DOKAZANA
Godine 1993. T. Feder i M. Vardi su formulisali Hipotezu o dihotomiji Problema zadovoljenja uslova. Jednostavna ekvivalentna formulacija je da za svaki konačan orijentisan graf H, problem da li postoji homomorfizam iz ulaznog konačnog orijentisanog grafa G u H ima samo jednu od dve složenosti, polinomnu ili NP-kompletnu. Ova hipoteza je motivisana deskriptivnom teorijom složenosti, a ima široke primene, pa i u praktičnim aspektima rada određenih velikih sistema kao što je francuska telekomunikaciona kompanija.
Prošle godine su objavljena na internetu čak četiri nezavisna dokaza Hipoteze. Dva su netačna, ali preostala dva, čiji autori su Andrej Bulatov, odnosno Dmitrij Žuk, su najverovatnije tačna. U ovom predavanju pokushaću da predstavim značaj rezultata i dam neku predstavu o tehnikama i strategiji dokaza u oba tačna dokaza, kao i greške na kojima su preostala dva pala.
Oba dokaza fundamentalno koriste pojam polimorfizma koji povezuje oblast univerzalne algebre sa konačnim modelima, dakle sa deskriptivnom složenošću, i daju istu karakterizaciju slučaja kad je problem u P.
Ovo predavanje je prerađena verzija predavanja koje sam održao na konferenciji Matematika i primene u decembru 2017.


PETAK, 25.05.2018. U 14:15, Matematicki institut SANU, sala 301f
Zoran Petric, Matematicki institut SANU
POTPUNOST
Rezultati potpunosti su svakako veoma bitni doprinosi logike. Oni se obicno odnose na formalne sisteme cijim teoremama "hvatamo" sve formule koje vaze u nekom modelu ili nekoj klasi modela. Medjutim, ako se bavimo teorijom dokaza, potpunost se odnosi na modele izvodjenja koji dobro opisuju jednakost (ili svodjenje) dokaza. Dacemo primere nekoliko algebarskih i topoloskih modela izvodjenja i opisati rezultate potpunosti vezane za njih.

OBAVESTENJA:

Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: tane@mi.sanu.ac.rs. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.rs



Beograd,
Srdacan pozdrav,

rukovodilac seminara Predrag Tanovic