Odeljenje za matematiku, 6. decembar 2013.

• 02. Decembar,  2013
• Komentari (0)

Naredni sastanak seminara biće održan u petak, 6. decembar 2013. sa početkom u 14 časova u sali 301f, Matematičkog instituta SANU.

Predavač: Petar Marković, Departman za matematiku i informatiku PMF, Novi Sad

Naslov predavanja: UVOD U DESKRIPTIVNU TEORIJU RAČUNSKE SLOŽENOSTI

Sadržaj: Godine 1974. R. Fagin je dokazao da je skup svojstava izrazivih u egzistencijalnom fragmentu logike drugog reda jednak klasi računske složenosti NP (nedeterministički polinimna).

Od te teoreme počinje oblast računske složenosti koja povezuje razne logičke sisteme sa klasama računske složenosti.

Iz tačke gledišta predavača (priučenog amatera u ovoj temi), izgleda da se ova oblast primarno razvijala u dva pravca: "ulepšavanje klase NP" koje je išlo ka nalaženju sve restriktivnijih logičkih sistema koji se takođe poklapaju sa klasom NP, ili bar imaju neprazan presek sa svakom klasom složenosti unutar NP, i "prevođenje logike na jezik teorije složenosti" gde se različiti prirodni fragmenti logike prvog i drugog reda na sličan način kao kod Fagina povezuju sa klasama računske složenosti.

Prvi pravac, svakako, ima za motivaciju napad na milenijumski problem $P=?NP$, dok je drugi dao jednu bogatu menažeriju novih klasa složenosti sa kojima se danas radi, te je i jedan od najpoznatijih preglednih internet sajtova o ovoj oblasti nazvan "Complexity Zoo".

Daćemo kratak pregled odabranih rezultata u oba pravca od 1974. do danas.

---