|
|
|
|||||||
| Év szerint | Hónap szerint | Ugrás a hónaphoz | |||||||
Bodor Bertalan: Johnson-gráfok reduktjai |
|
|||
|
|
||||
|
||||
| Absztrakt: Egy A relációs struktúra feletti CSP (Constraint Satisfaction Problem) a következő eldöntési probléma. Adott egy primitív pozitív formula phi az A struktúra szignatúrájában, és eldöntendő, hogy phi igaz-e az A struktúrában. Bulatov és Zhuk híres eredménye szerint tudjuk, hogy amennyiben A véges, akkor CSP(A)-ra teljesül egy bonyolultságdichotómia: az összes ilyen probléma P-ben van vagy NP-teljes. Ezen eredményen felbuzdulva felmerül a kérdés, hogy az előbbi dichotómia mikor és hogyan általánosítható végtelen struktúrákra. Az előadásomban ennek a problémának egy speciális esetéről fogok beszélni. Tekintsük azt a színezett gráfot, amelynek csúcsai a természetes számok k elemű részhalmazai, és két csúcs olyan színű éllel van összekötve, mint ami a metszetük számossága. Az előadásomon során leírom ezen struktúráknak az elsőrendű reduktjait, és belátom, hogy az összes ilyen reduktnak a CSP-je vagy NP-nehéz vagy ekvivalens egy korábban vizsgált CSP-vel, amire már ismert a fenti bonyolultságdichotómia. Az eredményből érdekes dolgok primitív pozitív definiálhatósága is következik, ezek közé tartozik például a 2023-as Schweitzer-verseny 7. feladatának állítása is. |
||||
Esemény exportálása JEvents v3.1.8 Stable Copyright © 2006-2013