Bejelentkezés
 Fórum
 
 
Témakiírás
 
Maróti Miklós
Algebra és algoritmikus problémák

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
matematika- és számítástudományok
Matematika- és Számítástudományok Doktori Iskola

témavezető: Maróti Miklós
helyszín: 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

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2318 ( 2016. XI. 26. )