Seminar za matematičku logiku i osnove matematike
Na Seminaru za matematičku logiku i osnove matematike, u ponedjeljak 16.
listopada 2017. u 17 sati, u predavaonici 105, PMF-MO, Luka Mikec će
održati predavanje
PSPACE-složenost logike interpretabilnosti (2)
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.
Predavanje se može pratiti i on-line na sljedećoj adresi:
https://meduza.carnet.hr/index.php/media/watch/11640.