A monotonitásvizsgálatról és a 2-2 játszmás sejtésről

Eredeti címe:

On Monotonicity Testing and the 2-to-2 Games Conjecture

Könyv tartalma:

Ez a könyv a komplexitáselmélet két kérdését tárgyalja: a monotonitás tesztelésének problémáját és a 2-2 játszma sejtését.

A monotonitásvizsgálat egy probléma a tulajdonságvizsgálat területéről, amelyet először Goldreich et al. vizsgált 2000-ben. Az algoritmus bemenete egy függvény, és a cél egy olyan tesztelő megtervezése, amely a lehető legkevesebb lekérdezést teszi a függvényre, monoton függvényeket fogad el, és monotonitástól távol eső függvényeket utasít el 1 közeli valószínűséggel.

A könyv első eredménye egy lényegében optimális algoritmus erre a problémára. Az algoritmus elemzése nagymértékben támaszkodik Talagrand 1993-as Boole-izoperimetrikus egyenlőtlenségének újszerű, irányított és robusztus analógiájára.

A valószínűségileg ellenőrizhető bizonyítások (PCP) tétele a modern elméleti informatika egyik sarokköve. Az egyik terület, ahol a PCP-k nélkülözhetetlenek, a közelítés keménységének területe. Ebben az esetben a cél annak bizonyítása, hogy bizonyos optimalizálási problémák még közelítőleg is nehezen megoldhatók. A közelítés keménységének számos eredményét bizonyították a PCP-tétel segítségével, azonban néhány problémára nem kaptak optimális eredményeket. Ez a könyv néhány ilyen problémát érint, különösen a 2-2 játék problémáját és a vertexfedési problémát.

A könyv második eredménye a 2-2 játszmás játékok sejtésének bizonyítása (tökéletlen teljességgel), amely új közelítési eredmények keménységét implikálja olyan problémákra, mint a vertexfedés és a független halmaz. Emellett erős bizonyítékként szolgál az egyedi játszmák sejtése felé, amely az elméleti informatika egyik hírhedt, kapcsolódó nyitott problémája. A bizonyítás középpontjában a Grassmann-gráfok kis csúcshalmazainak jellemzése áll, amelyek élkiterjesztése 1-től elfelé korlátos.