Czy istnieje prosty argument, który pokazuje, że unikalna hipoteza gier implikuje twierdzenie PCP

17

jak można pokazać, jaki jest związek między „hipotezą o unikalnych grach” a „twierdzeniem PCP”? jak tłumaczyć „hipoteza o unikalnych grach” jest silniejszą formą „twierdzenia PCP”?

js
źródło

Odpowiedzi:

19

Odnośny -conjecture z KHOT oznacza twierdzenie PCP z doskonałą kompletności: oczekuje się, że dowód otrzymując etykietowania wierzchołków. Weryfikator wybiera losową krawędź, która wysyła zapytania do swoich punktów końcowych i akceptuje, jeśli ograniczenie jest spełnione.2)-1

Aby uzyskać twierdzenie PCP z doskonałą kompletnością na podstawie unikalnego przypuszczenia dotyczącego gier, musisz, jak pisze Boaz, przekształcić PCP w jedno z doskonałą kompletnością. Jednym ze sposobów na to jest:(do,s)

(1-do)m(1-s)m

Irit Dinur
źródło
22

Zależy to trochę od tego, jak zdefiniujesz Twierdzenie PCP, czy jest ono całkowicie kompletne, czy nie. Jak stwierdzamy w naszej książce, równoważną formą twierdzenia PCP jest to, że istnieje pewien problem związany z satysfakcją z ograniczeń, dla którego trudno jest odróżnić idealny przypadek satysfakcjonujący od przypadku, który można zaspokoić co najwyżej ułameks<1uwarunkowań. Moglibyśmy jednak podać wariant o niedoskonałej kompletności, zastępując idealnie zadowalającą skrzynkę zdolnością zaspokoić pewną częśćdo>s.

Unikalna hipoteza gier jest założeniem tej drugiej formy (gdzie, dzięki czemu warunek jest silniejszy do jest blisko do 1 i s jest blisko do 0) i, co najważniejsze, ograniczenia mają bardzo specjalną formę (ograniczenia permutacji dwóch zmiennych). W tym sensie jest to (zasadniczo) silniejsza forma twierdzenia PCP.

Możesz zapytać, czy istnieje łatwa transformacja, aby przekonwertować PCP z niedoskonałą kompletnością na taką z idealną kompletnością. Myślę, że można to zrobić łatwiej niż udowodnienie twierdzenia PCP, ale w tej chwili nie jestem świadomy bardzo prostego argumentu.

Boaz Barak
źródło