Exemple pour un PCP non négligeable pour un vérificateur problème NP-complet

Question

Au cours de ma participation à un cours sur le traitement des problèmes NP-difficiles, je l'ai rencontré le théorème PCP, indiquant

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

Je comprends la définition technique d'un vérificateur PCP, donc je sais en principe ce genre d'algorithme doit exister pour chaque problème NP: un algorithme aléatoire qui contrôle O $ (1) $ bits du certificat donné pour l'entrée donnée en utilisant $ O (\ log n) $ bits aléatoires, de sorte que cet algorithme est essentiellement un Monte-Carlo erreur unilatérale vérificateur.

Cependant, j'ai du mal à imaginer comment un tel algorithme peut faire face à un problème NP-complet. Court de lire la preuve du théorème PCP, y at-il des exemples concrets de ces algorithmes?

I écrémé les sections pertinentes du Complexité: A Modern Approach par Arora et Barak (2009), mais ne trouve pas.

Un exemple en utilisant un $ \ mathsf {PCP} (\ _, \ ll n) algorithme $ serait bien.

Answer 1

Faisant suite à un commentaire par sdcvvc J'ai vérifié par exemple 11,7 dans complexité: une approche moderne par Arora et Barak ( Projet de 2008). Là, les auteurs décrivent un "algorithme de PCP" pour le problème Graphique non-Isomorphisme (RNB):

Entrée: deux graphiques $ G_0 $ et $ G_1 $ avec $ n sommets $ chacun

.

Sortie: Accepter si et seulement si $ G_0 $ et $ G_1 $ ne sont pas isomorphe (écrire $ G_0 \ not \ equiv G_1 $).

Nous noterons le certificat (ils l'appellent "preuve") par $ \ pi $ et $ \ pi (i) $ $ i $ -ème bit de $ \ pi $.

L'algorithme $ A $ se déroule comme suit:

• Choisissez un peu $ b \ in \ {0,1 \} $ uniformément au hasard.
• Choisir une permutation $ \ sigma \ dans S_n $ (des sommets de G_b $ $).
• Accepter si $ \ pi (\ langle \ sigma (G_b) \ rangle) = b $, rejeter autrement.

Ici, $ \ langle \ _ \ rangle $ est une bijection calculable à partir de $ \ mathbb {N} ^ n $ à une gamme appropriée de $ [0..n] \ subseteq \ mathbb {N} $ de. Nous partons du principe que si le derefenced bit $ \ pi $ n'existe pas, à savoir le certificat est trop court, nous rejetons.

Claim: Par algorithme ci-dessus, le RNB est en $ \ operatorname {PCP} (n \ log n, 1) $, i.e.

.

1. l'algorithme utilise O $ (n \ log n) $ bits aléatoires et des requêtes O $ (1) $ bits de $ \ pi $,
2. $ (G_0, G_1) \ in \ mathrm {RNB} $ implique qu'il existe un certificat $ \ pi $ de sorte que $ \ Pr [A (G_0, G_1, \ pi) \ texte {} accepte] = 1 $ et
3. $ (G_0, G_1) \ Notin \ mathrm {RNB} $ implique que $ \ Pr [A (G_0, G_1, \ pi) \ texte {} rejette] \ geq \ frac {1} {2} $ pour tous certificats $ \ Pi \ in \ {0,1 \} ^ * $.

Annonce 1: Effacer de l'algorithme en notant que l'échantillonnage de permutation uniforme est possible avec $ \ environ n \ log n $ bits¹ aléatoire.

Annonce 2: Considérez le certificat

$ \ qquad \ displaystyle \ pi (\ langle H \ rangle) = \ Begin {cas} 0 &, H \ de G_0, H \ ne \ equiv G_1 \\ 1 &, H \ s G_1, H \ not \ \\ équiv G_0 \ Texte {} arbitraire et, \ texte {} autrement \ End {cas} $

où $ H $ sont tous les graphiques avec $ n $ nœuds. Depuis G_0 $ \ not \ equiv G_1 $ et $ \ Sigma (G_b) \ equiv G_b $, nous avons $ \ sigma (G_b) \ not \ equiv G_ {1-b} $ pour tous $ b $ et $ \ Sigma $. La requête à $ \ pi $ donne donc toujours $ b $ et donc toujours accepter.

Annonce 3: Soit $ \ pi \ in \ {0,1 \} ^ * = $ arbitraire et $ H \ sigma (G_b) $ l'Elu graphique requête. Si notre requête frappe un bit non existant de $ \ pi $ que nous rejetons par hypothèse, qui est correct. Dans le cas contraire, on calcule

$ \ qquad \ begin {align} \ Pr [\ texte {accept}] & = \ 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 \ mi 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]} \droite) \\ & = \ Frac {1} {2} \ End {align} $ à l'aide que $ H \ equiv G_1 \ ssi H \ equiv G_0 $ dans ce cas.

Ainsi, la demande est prouvée.

---

Quelques observations qui me ont aidé à saisir ces concepts mieux.

• Le certificat $ \ pi $ peut être arbitrairement longue et arbitrairement complexe. Notez que certificats « bien » pour l'algorithme ci-dessus résolvent essentiellement le même problème comme l'algorithme (plusieurs fois).
• Mais cela ne signifie pas que tout problème de décision peut être résolu dans le style PCP par « juste fournir la réponse dans le certificat ». Condition 3 empêche tout tentative naïve de ce genre.
• Il est dans les genresl pas possible d'obtenir une efficacité (aléatoire unilatérale d'erreur) algorithme qui devine le certificat (comme cela est le cas pour les certificats-NP vérificateurs).

---

1. A proprement parler, cela suppose que $ n! = 2 ^ k $ (ce qui bien sûr tient presque jamais) puisque nous infini pire avez cas d'exécution pour d'autres $ n $. Cependant, semble Arora / Barak d'ignorer cet aspect.

Answer 2

Deux problèmes qui surgissent pourrait aider à l'intuition:

1. Montrer que $ \ {mathsf AM} \ subseteq \ mathsf {PCP} (\ texte {poly} (n), 1) $. Vous êtes autorisé à assumer $ \ mathsf {NP} \ subseteq \ mathsf {PCP} (\ texte {poly} (n), 1) $.

2. Montrer que $ \ mathsf {PSPACE} \ subseteq \ mathsf {PCP} (\ texte {poly} (n), \ texte {poly} (n)) $. Conseil:

Utilisez IP = PSPACE

Anecdote: Le premier exercice subsume le PCP pour le RNB, tandis que le second subsume le PCP pour permanent. Les deux résultats sont englobés par $ \ {mathsf NEXP} = \ {mathsf PCP} (\ texte {poly} (n), 1) $.