Gibt es ein einfaches Argument, das zeigt, dass die Vermutung der einzigartigen Spiele das PCP-Theorem impliziert?

Wie kann man zeigen, in welcher Beziehung "Unique Games Conjecture" und "PCP Theorem" zueinander stehen? Wie erklärt man, dass "Unique Games Conjecture" eine stärkere Form des "PCP-Theorems" ist?

$2-1$ Hypothese von Khot impliziert das PCP-Theorem mit absoluter Vollständigkeit: Der Beweis soll eine Beschriftung der Eckpunkte ergeben. Der Prüfer wählt eine zufällige Kante aus, fragt ihre Endpunkte ab und akzeptiert, wenn die Einschränkung gilt.

$(c,s)$

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

Es kommt ein bisschen darauf an, wie Sie das PCP-Theorem definieren, ob es vollständig ist oder nicht. Wie wir in unserem Buch festhalten, gibt es eine äquivalente Form des PCP-Theorems: Es gibt ein Problem der Beschränkungszufriedenheit, für das es schwer ist, zwischen dem perfekt erfüllbaren Fall und dem Fall zu unterscheiden, den man höchstens mit einem Bruchteil erfüllen kann$s<1$der cosntraints. Wir hätten aber eine Variante mit unvollständiger Aussage machen können, die den vollkommen erfüllbaren Fall durch die Möglichkeit ersetzt, einen Bruchteil zu befriedigen$c>s$.

Die einzigartige Spielvermutung ist eine Annahme dieser letzteren Form (wobei der Zustand stärker wird) $c$ liegt in der Nähe $1$ und $s$ liegt in der Nähe $0$) und vor allem haben die Bedingungen eine sehr spezielle Form (Permutationsbedingungen für zwei Variablen). In diesem Sinne ist es die (wesentlich) stärkere Form des PCP-Theorems.

Sie können sich fragen, ob es eine einfache Umwandlung gibt, um ein PCP mit unvollständiger in ein PCP mit perfekter Vollständigkeit umzuwandeln. Ich denke, es ist wahrscheinlich einfacher, als das PCP-Theorem zu beweisen, aber mir ist im Moment kein sehr einfaches Argument bekannt.