Seminar za matematičku logiku i osnove matematike

Lokacija: 
PMF Matematički odsjek
Vrijeme: 
Ponedjeljak, 9 Listopad, 2017 - 17:00

Na Seminaru za matematičku logiku i osnove matematike, u ponedjeljak 9. listopada 2017. u 17 sati, u predavaonici 104, PMF-MO, Luka Mikec će održati predavanje

PSPACE-složenost logike interpretabilnosti


Sažetak:
O složenosti logike interpretabilnosti IL je poznato da je njezin zatvoreni fragment (bez varijabli) PSPACE-težak. Dokazat ćemo da IL pripada klasi PSPACE, a kao posljedicu tada imamo PSPACE-potpunost. Komentirat ćemo složenost nekih proširenja logike interpretabilnosti IL.

Go to top