témavezető: Maróti Miklós
helyszín (magyar oldal): SZTE TTIK Matematika- és Számítástudományok Doktori Iskola 6720 Szeged, Aradi vértanúk tere 1. helyszín rövidítés: MatDI
A kutatási téma leírása:
Algebrai eszközök nagy sikerrel alkalmazhatók klasszikus algoritmikus problémák vizsgálatára, mint például az struktúra homomorfizmus (általánosított gráfszinezési) probléma komplexitásának meghatározására. Tudott, hogy bizonyos Malcev-fetételek teljesülése esetén ez a probléma polinomiális időben megoldható, illetve ha az úgynevezett "gyönge többségi függvény" Malcev-feltétel nem teljesül, akkor a probléma NP-teljes. A kombinatorika, univerzális algebra és komplexitáselmélet ezen határterületének vizsgálata nagyon sok érdekes és nehéz problémát vetett fel, többek között Feder és Vardi 15 éve nyitott dichotómia sejtését. Algebrai probémák komplexitásának vizsgálata mellett azok (varietások azonosság, illetve szóproblémája, Malcev-feltételek teljesülése) eldönthetősége is nagyon széles kutatási terület számos nyitott problémával.
felvehető hallgatók száma: 1
Jelentkezési határidő: 2016-11-30
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
