Thesis supervisor: Miklós Maróti
Location of studies (in Hungarian): SZTE TTIK Matematika- és Számítástudományok Doktori Iskola 6720 Szeged, Aradi vértanúk tere 1. Abbreviation of location of studies: MatDI
Description of the research topic:
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.
Number of students who can be accepted: 1
Deadline for application: 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).
Login
