O testowaniu monotoniczności i przypuszczeniu gier 2 na 2

Oryginalny tytuł:

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

Zawartość książki:

Ta książka omawia dwa zagadnienia z teorii złożoności: problem testowania monotoniczności i przypuszczenie gier 2-do-2.

Testowanie monotoniczności to problem z dziedziny testowania własności, po raz pierwszy rozważony przez Goldreicha et al. w 2000 roku. Wejściem algorytmu jest funkcja, a celem jest zaprojektowanie testera, który wykonuje jak najmniej zapytań do funkcji, akceptuje funkcje monotoniczne i odrzuca funkcje dalekie od monotonicznych z prawdopodobieństwem bliskim 1.

Pierwszym rezultatem tej książki jest zasadniczo optymalny algorytm dla tego problemu. Analiza algorytmu w dużym stopniu opiera się na nowym, ukierunkowanym i solidnym odpowiedniku boolowskiej nierówności izoperymetrycznej Talagranda z 1993 roku.

Twierdzenie o probabilistycznie sprawdzalnych dowodach (PCP) jest jednym z kamieni węgielnych współczesnej informatyki teoretycznej. Jednym z obszarów, w którym PCP są niezbędne, jest twardość aproksymacji. Celem jest udowodnienie, że niektóre problemy optymalizacyjne są trudne do rozwiązania, nawet w przybliżeniu. Wiele wyników dotyczących twardości aproksymacji zostało udowodnionych przy użyciu twierdzenia PCP, jednak dla niektórych problemów nie uzyskano optymalnych wyników. Niniejsza książka porusza niektóre z tych problemów, w szczególności problem gier 2 na 2 i problem pokrycia wierzchołków.

Drugim rezultatem tej książki jest dowód przypuszczenia o grach 2-do-2 (z niedoskonałą kompletnością), który implikuje nowe wyniki twardości aproksymacji dla problemów takich jak pokrycie wierzchołków i zbiór niezależny. Służy on również jako mocny dowód w kierunku przypuszczenia o unikalnych grach, znanego powiązanego otwartego problemu w informatyce teoretycznej. Sednem dowodu jest charakterystyka małych zbiorów wierzchołków w grafach Grassmanna, których rozwinięcie krawędzi jest ograniczone z dala od 1.