M1, 2005–2006

Complexité structurelle – TD 12 Probabilistically checkable proofs

On rappelle ci-après la définition des classes PCP. L ∈ PCP(r(n), q(n)) s’il existe un vérificateur V, utilisant r(n) bits aléatoires et lisant q(n) bits de la preuve de manière non-adaptative, tel que :

– si x ∈ L alors il existe une preuve Π tel que V^{Π}(x) accepte toujours ;

– si x ∉ L alors pour toute preuve Π, Proba(V^{Π}(x) accepte) ≤ 1/2. On rappelle enfin le théorème PCP :

NP = PCP(O(log n), O(1)).

Exercice 1 Max-k-CSP est le problème suivant : étant données les tables de vérité de t fonctions booléennes f_{1}, …, f_{t} d’arité k sur n variables, retourner une affectation qui maximise le nombre de f_{i} satisfaites. Montrer que Max-k-CSP est NP-complet dès que k ≥ 3. En admettant le théorème PCP, montrer qu’il existe k tel que pour tout ϵ > 0, si l’on peut (2 − ϵ)-approximer Max-k-CSP, alors P = NP.

Soit QPSAT le langage constitué de l’ensemble des uples de polynômes (f_{1}, …, f_{n}), où les f_{i} ∈ F_{2}[X_{1}, …, X_{n}] sont de degré ≤ 2, tels qu’il existe une racine commune :

∃a ∈ (F_{2})^{n} tel que ⋀_{i=1}^{n}(f_{i}(a) = 0).

Exercice 2 Le but de cet exercice est de montrer que NP = PCP(n^{O(1)}, O(1)).

1. Montrer que QPSAT est NP-complet. Dans la suite, on va montrer que QPSAT ∈ PCP(O(n^{2}), O(1)).

2. Pourquoi l’idée naïve de donner comme preuve la racine commune ne fonctionne pas ?

3. Pour r, a ∈ (F_{2})^{n} on pose Q(r, a) = ∑_{i} r_{i}f_{i}(a). Avec quelle probabilité sur r a-t-on Q(r, a) = 0 ?

4. Puisque le degré de Q(r, .) est ≤ 2, à r fixé on peut écrire

Q(r, a) = α + (^{t}β)a + (^{t}a)γa,

où α est un scalaire de F_{2}, β un vecteur et γ une matrice. On fournit la preuve Π = (Π_{1}, Π_{2}), avec

Π_{1} = (^{t}βa)_{β∈(F_{2})^{n}} et Π_{2} = (^{t}aγa)_{γ∈(F_{2})^{n×n}}.

Proposer un algorithme pour le vérificateur. Pourquoi ça ne marche toujours pas ?

5. Il faut que β ↦ Π_{1}(β) soit linéaire, ainsi que γ ↦ Π_{2}(γ). Supposons que ce soit le cas. Il faut par ailleurs que Π_{1} et Π_{2} soient définis à partir du même a. Proposer un test pour cela. Pour prouver la correction de ce test, on pourra étudier la probabilité sur r, r′ que (^{t}r)Ar′ = (^{t}r)Br′ pour deux matrices A et B différentes.

6. Proposer un test probabiliste de linéarité : il s’agit de vérifier qu’une fonction f donnée par un oracle est linéaire.

7. Résumer le protocole. Note : il faut en plus utiliser une « auto-correction » des fonctions Π_{1} et Π_{2}. Pour évaluer une fonction f (prétendue linéaire) sur x, l’autocorrection consiste à retourner la valeur f(x+y)−f(y) avec un y choisi aléatoirement.