Beispiel für eine nicht-triviale PCP verifier für ein NP-vollständiges problem

Question

Während meiner Teilnahme an einem Kurs zum Umgang mit NP-harten Probleme habe ich festgestellt das PCP-theorem, besagt

$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.

Ich verstehe die technische definition eines PCP-verifier, so weiß ich im Prinzip, welche Art von Algorithmus hat zu existieren für jedes NP-problem:ein randomisierter Algorithmus, der prüft, $O(1)$ bits der gegebene Zertifikat für die angegebene Eingabe mit $O(\log n)$ zufälligen bits, so dass dieser Algorithmus ist im wesentlichen eine einseitige Fehler Monte-Carlo-textprüfung.

Ich habe allerdings Schwierigkeiten, sich vorzustellen, wie ein solcher Algorithmus kann mit einem NP-vollständigen problem.Kurze Lesung der Beweis des PCP-theorems, gibt es konkrete Beispiele für solche algorithmen?

Ich Griff in den betreffenden Abschnitten Computational Komplexität:Ein Moderner Ansatz von Arora und Barak (2009) fanden aber keine.

Ein Beispiel mit einem $\mathsf{PCP}(\_,\ll n)$ - Algorithmus wäre in Ordnung.

Answer 1

Folgenden bis auf ein Kommentar von sdcvvc Ich checkte aus Beispiel 11.7 in Computational Komplexität:Ein Moderner Ansatz von Arora und Barak (Entwurf 2008).Dort beschreiben die Autoren ein "PCP-Algorithmus" für das problem Graph Nicht-Isomorphie (BNE):

Eingang: Zwei Graphen $G_0$ und $G_1$ mit $n$ Scheitelpunkten jeder.

Ausgabe: Akzeptieren, wenn und nur wenn $G_0$ und $G_1$ sind nicht isomorph (schreiben $G_0 icht\equiv G_1$).

Wir bezeichnen das Zertifikat (Sie nennen es "Beweis") von $\pi$ und $\pi(i)$ die $i$-te bit von $\pi$.

Der Algorithmus $A$ verläuft wie folgt:

• Wählen Sie ein bisschen $b \in \{0,1\}$ einheitlich nach dem Zufallsprinzip.
• Wählen Sie eine permutation $\sigma \in S_n$ (der Scheitelpunkte von $G_b$).
• Akzeptieren, wenn $\pi(\langle\sigma(G_b) angle) = b$, ablehnen anders.

Hier ist $\langle \_ angle$ ist etwas berechenbar bijection von $\mathbb{N}^n$ um einen geeigneten Bereich $[0..N] \subseteq \mathbb{N}$.Wir gehen davon aus, dass, wenn die derefenced bit in $\pi$ nicht vorhanden ist, d.h.das Zertifikat ist zu kurz, lehnen wir ab.

Anspruch: Durch den oben beschriebenen Algorithmus, BNE in $\operatorname{PCP}(n \log n, 1)$, D. H.

1. der Algorithmus $O(n \log n)$ random bits und Abfragen $O(1)$ bits von $\pi$,
2. $(G_0, G_1) \in \mathrm{BNE}$ impliziert, dass es einige Zertifikat $\pi$ so, dass $\Pr[A(G_0, G_1, \pi) ext{ akzeptiert}] = 1$, und
3. $(G_0, G_1) otin \mathrm{BNE}$ impliziert, dass $\Pr[A(G_0, G_1, \pi) ext{ ablehnt}] \geq frac{1}{2}$ für alle Zertifikate $\pi \in \{0,1\}^*$.

Ad 1: Klar, aus dem Algorithmus mit der Feststellung, dass gleichmäßige permutation sampling ist es möglich, mit $\approx n \log n$ random bits1.

Ad 2: Betrachten Sie das Zertifikat

$\qquad\displaystyle \pi(\langle H angle) = \begin{Fälle} 0 &, H \equiv G_0, H icht\equiv G_1 \\ 1 &, H \equiv G_1, H icht\equiv G_0 \\ ext{beliebig} &, ext{ sonst} \end{Fälle}$

wobei $H$ sind alle Graphen mit $n$ - Knoten.Da $G_0 icht\equiv G_1$ und $\sigma(G_b) \equiv G_b$, wir haben $\sigma(G_b) icht\equiv G_{1-b}$ für alle $b$ und $\sigma$.Die Abfrage auf $\pi$ ist daher immer ergibt $b$ und somit immer akzeptieren.

Ad 3: Lassen Sie $\pi \in \{0,1\}^*$ willkürlich ist und $H = \sigma(G_b)$ die gewählte query graph.Wenn unsere Abfrage trifft einen nicht-existierenden bit von $\pi$, die wir ablehnen, indem Annahme, das ist richtig.Sonst, wir berechnen

$\qquad\begin{align} \Pr[ ext{akzeptiert}] &= \Pr[b=0] \cdot \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]} + \Pr[b=1] \cdot \frac{\#[\pi(H) = 1 \mid H \equiv G_1]}{\#[H \equiv G_1]} \\ &= \frac{1}{2} \cdot \left( \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]} + \frac{\#[\pi(H) = 1 \mid H \equiv G_0]}{\#[H \equiv G_0]} echts) \\ &= \frac{1}{2} \end{align}$ verwenden, dass $H \equiv G_1 \iff H \equiv G_0$ in diesem Fall.

So kann die Behauptung ist bewiesen.

---

Einige Beobachtungen, die mir geholfen haben das Verständnis dieser Konzepte besser.

• Das Zertifikat $\pi$ können beliebig lang sein und beliebig Komplex sein.Beachten Sie, dass "gut" Zertifikate für die oben beschriebenen Algorithmus im wesentlichen dasselbe problem zu lösen da der Algorithmus (viele Male).
• Aber das bedeutet nicht, dass jede Entscheidung, die problem gelöst werden kann in PCP-Stil von "liefern die Antwort in dem Zertifikat".Zustand 3 verhindert naive Versuch, die Art.
• Es ist im Allgemeinen nicht möglich, daraus eine effiziente (randomisierte one-sided error) Algorithmus, der errät das Zertifikat (wie bei NP-Zertifikat-Verifizierer).

---

1. Streng genommen, dies setzt Voraus, dass $n!=2^k$ (was natürlich fast nie hält) da wir unendliche worst-case-Laufzeit für andere $n$.Allerdings Arora/Barak scheinen zu ignorieren diesen Aspekt.

Answer 2

Zwei Probleme, die dazu beitragen könnten, Intuition zu entwickeln:

1. Beweisen Sie, dass $ mathsf {am} subseteq mathsf {PCP} ( text {poly} (n), 1) $. Sie dürfen $ mathsf {np} subseteq mathsf {PCP} ( text {poly} (n), 1) $ annehmen.

2. Beweisen Sie, dass $ mathsf {Pspace} subseteq mathsf {PCP} ( text {poly} (n), text {poly} (n)) $. Hinweis:

Verwenden Sie IP = PSPACE

TRIVIA: Die erste Übung fasst den PCP für GNI ab, während der zweite den PCP für dauerhaft abbaut. Beide Ergebnisse werden von $ mathsf {nexp} = mathsf {PCP} ( text {poly} (n), 1) $ subsumiert.