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

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”?

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:$(c,s)$

$(1-c)\cdot m$$(1-s)\cdot m$

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łamek$s<1$uwarunkowań. Moglibyśmy jednak podać wariant o niedoskonałej kompletności, zastępując idealnie zadowalającą skrzynkę zdolnością zaspokoić pewną część$c>s$.

Unikalna hipoteza gier jest założeniem tej drugiej formy (gdzie, dzięki czemu warunek jest silniejszy $c$ 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.