O testovaní monotónnosti a domnienke o hrách 2:2

Pôvodný názov:

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

Obsah knihy:

Táto kniha sa zaoberá dvoma otázkami z teórie zložitosti: problémom testovania monotónnosti a domnienkou o hrách 2 na 2.

Testovanie monotónnosti je problém z oblasti testovania vlastností, ktorým sa prvýkrát zaoberali Goldreich a kol. v roku 2000. Vstupom algoritmu je funkcia a cieľom je navrhnúť tester, ktorý vykoná čo najmenej dotazov na funkciu, akceptuje monotónne funkcie a od monotónnych funkcií vzdialené funkcie od monotónnych funkcií odmieta s pravdepodobnosťou blízkou 1.

Prvým výsledkom tejto knihy je v podstate optimálny algoritmus pre tento problém. Analýza algoritmu sa vo veľkej miere opiera o novú, adresnú a robustnú analógiu Talagrandovej boolovskej izoperimetrickej nerovnosti z roku 1993.

Veta o pravdepodobnostne kontrolovateľných dôkazoch (PCP) je jedným zo základných kameňov modernej teoretickej informatiky. Jednou z oblastí, v ktorej sú PCP nevyhnutné, je oblasť tvrdosti aproximácie. V nej je cieľom dokázať, že niektoré optimalizačné problémy sú ťažko riešiteľné, a to aj približne. Mnohé výsledky tvrdosti aproximácie boli dokázané pomocou vety o PCP; pre niektoré problémy sa však optimálne výsledky nedosiahli. Táto kniha sa dotýka niektorých z týchto problémov, a to najmä problému hier 2 na 2 a problému vrcholového pokrytia.

Druhým výsledkom tejto knihy je dôkaz domnienky o 2-to-2 hrách (s nedokonalou úplnosťou), z ktorej vyplývajú nové výsledky tvrdosti aproximácie pre problémy ako vrcholový kryt a nezávislá množina. Slúži tiež ako silný dôkaz smerom k domnienke o jedinečných hrách, čo je notoricky známy súvisiaci otvorený problém v teoretickej informatike. Jadrom dôkazu je charakterizácia malých množín vrcholov v Grassmannových grafoch, ktorých hranové rozšírenie je ohraničené od 1.