Esempio di PCP non banale verificatore per un problema NP-completo

Question

Durante la mia partecipazione a un corso su come affrontare i problemi NP-hard che ho incontrato il teorema PCP, indicando

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

ho capito la definizione tecnica di una PCP verificatore, quindi so in linea di principio che tipo di algoritmo deve esistere per ogni problema NP: un algoritmo randomizzato che i controlli $ O (1) $ bit del certificato di data per l'ingresso data utilizzando $ O (\ log n) $ bit casuali, in modo che questo algoritmo è essenzialmente un'unilaterale errore Monte-Carlo verificatore.

Tuttavia, devo immaginare problemi come un tale algoritmo in grado di affrontare un problema NP-completo. Breve lettura della dimostrazione del teorema PCP, ci sono esempi concreti di tali algoritmi?

I scremato relative sezioni complessità computazionale: A Modern Approach da Arora e Barak (2009), ma non ha trovato alcuna.

Un esempio utilizzando un mathsf $ \ {} PCP (\ _, \ ll n) $ algoritmo andrebbe bene.

Answer 1

In seguito ad un commento di sdcvvc ho verificato esempio 11.7 in complessità computazionale: a Modern Approach da Arora e Barak ( Progetto del 2008). Lì, gli autori descrivono un "algoritmo PCP" per il problema Graph non Isomorfismo (RNL):

ingresso: due grafici $ G_0 $ e $ G_1 $ con $ n vertici $ ogni

.

Output: Accetta se e solo se $ G_0 $ e $ G_1 $ non sono Isomorph (write $ G_0 \ Non \ equiv G_1 $).

Indichiamo il certificato (lo chiamano "prova") per $ \ pi $ e $ \ pi (i) $ il $ i $ -esimo po 'di $ \ pi $.

L'algoritmo di $ A $ procede come segue:

• Scegli un po '$ b \ in \ {0,1 \} $ uniformemente a caso.
• Scegli una permutazione $ \ sigma \ a S_n $ (dei vertici di $ G_b $).
• Accept se $ \ pi (\ Langle \ sigma (G_b) \ rangle) = b $, rifiutare altrimenti.

Qui, $ \ langle \ _ \ $ rangle è una certa corrispondenza biunivoca calcolabile da $ \ mathbb {N} ^ n $ ad una gamma adatta $ [0..n] \ subseteq \ mathbb {N} $. Partiamo dal presupposto che se il derefenced bit in $ \ pi $ non esiste, cioè il certificato è troppo breve, rifiutiamo.

Modifica Per algoritmo di cui sopra, RNL è in $ \ operatorname {} PCP (n \ log n, 1) $, cioè

.

1. l'algoritmo utilizza $ O (n \ log n) $ bit casuali e interroga $ O (1) $ bit di $ \ pi $,
2. $ (G_0, G_1) \ in \ mathrm {} RNL $ implica che ci sia qualche certificato di $ \ pi $ in modo tale che $ \ Pr [A (G_0, G_1, \ pi) \ text {} accetta] = 1 $, e
3. $ (G_0, G_1) \ notin \ mathrm {} RNL $ implica che $ \ Pr [A (G_0, G_1, \ pi) \ text {} scarti] \ geq \ tfrac {1} {2} $ per tutti certificati $ \ Pi \ in \ {0,1 \} ^ * $.

annuncio 1: Cancella dal algoritmo notando che il campionamento permutazione uniforme è possibile con $ \ circa n \ log n $ bits¹ casuale.

Ad 2: Si consideri il certificato

$ \ qquad \ displaystyle \ pi (\ langle H \ rangle) = \ Begin {casi} 0 &, H \ equiv G_0, H \ Non \ equiv G_1 \\ 1 &, H \ equiv G_1, H \ Non \ equiv G_0 \\ \ Text {} arbitrario e, \ text {altrimenti} \ End {casi} $

dove $ H $ sono tutti i grafici con $ n $ nodi. Dal momento che $ G_0 \ Non \ equiv G_1 $ e $ \ Sigma (G_b) \ equiv G_b $, abbiamo $ \ sigma (G_b) \ Non \ equiv G_ {1-b} $ per tutti i $ B $ e $ \ Sigma $. La query a $ \ pi $ produce quindi sempre $ B $ e quindi sempre accettare.

Ad 3: Sia $ \ pi \ in \ {0,1 \} ^ * $ arbitraria e $ H = \ sigma (G_b) $ la scelta interrogazione grafico. Se la nostra interrogazione colpisce un po 'non-esistente di $ \ pi $ rifiutiamo per ipotesi, che è corretto. In caso contrario, si calcola

$ \ qquad \ begin {align} \ Pr [\ text {accettare}] & = \ Pr [b = 0] \ cdot \ frac {\ # [\ pi (H) = 0 \ metà H \ equiv G_0]} {\ # [H \ equiv G_0] } + \ Pr [b = 1] \ cdot \ frac {\ # [\ pi (H) = 1 \ metà H \ equiv G_1]} {\ # [H \ equiv G_1]} \\ & = \ Frac {1} {2} \ cdot \ left (\ frac {\ # [\ pi (H) = 0 \ metà H \ equiv G_0]} {\ # [H \ equiv G_0]} + \ Frac {\ # [\ pi (H) = 1 \ metà H \ equiv G_0]} {\ # [H \ equiv G_0]} \giusto) \\ & = \ Frac {1} {2} \ End {align} $ usando che $ H \ equiv G_1 \ se e solo se H \ equiv G_0 $ in questo caso.

In questo modo, l'affermazione è provata.

---

Alcune osservazioni che mi hanno aiutato afferrare questi concetti meglio.

• Il certificato di $ \ pi $ può essere arbitrariamente lungo e arbitrariamente complessa. Nota che "Buoni" certificati per l'algoritmo sopra risolvono essenzialmente lo stesso problema come l'algoritmo (molte volte).
• Ma questo non implica che qualsiasi problema decisione può essere risolto in stile PCP da "solo fornendo la risposta nel certificato". Condizione 3 impedisce qualsiasi ingenuo tentativo di questo tipo.
• E 'in generil possibile ricavare un efficiente (randomizzato unilaterale-error) algoritmo che indovina il certificato (come è il caso per verificatori NP-certificato).

---

1. A rigor di termini, questo presuppone che $ n! = 2 ^ k $ (che ovviamente quasi mai stive) dal momento che Hanno infinita caso peggiore runtime per altri $ n $. Tuttavia, Arora / Barak sembrano ignorare questo aspetto.

Answer 2

Due problemi che potrebbero aiutare a sviluppare l'intuizione:

1. Dimostrare che $ \ mathsf {AM} \ subseteq \ mathsf {} PCP (\ text {} poli (n), 1) $. Hai il permesso di assumere $ \ {mathsf NP} \ subseteq \ mathsf {} PCP (\ text {} poli (n), 1) $.

2. Dimostrare che $ \ {mathsf PSPACE} \ subseteq \ mathsf {} PCP (\ text {} poli (n), \ text {} poli (n)) $. Suggerimento:

Usa IP = PSPACE

Curiosità: Il primo esercizio sussume il PCP per RNL, mentre la seconda sussume il PCP per permanente. Entrambi i risultati sono sussunti da $ \ {mathsf NEXP} = \ mathsf {} PCP (\ text {} poli (n), 1) $.