Les bons PCP pour NP nous donnent-ils de bons PCP pour toute la hiérarchie polynomiale?

Le théorème du PCP déclare que chaque problème de décision dans NP a des preuves probabilistes vérifiables (ou de manière équivalente, qu'il existe un système de preuve complet et quasi-sain pour les théorèmes dans NP utilisant une complexité de requête constante et logarithmiquement de nombreux bits aléatoires).

La «sagesse populaire» entourant le théorème du PCP (ignorant un instant l'importance du PCP pour la théorie de l'approximation) est que cela signifie que les preuves écrites dans un langage mathématique strict peuvent être vérifiées efficacement à tout degré de précision souhaité sans avoir à lire l'intégralité preuve (ou une grande partie de la preuve du tout).

Je ne peux pas vraiment voir cela. Considérez l'extension de second ordre à la logique propositionnelle avec une utilisation illimitée de quantificateurs (dont on me dit qu'elle est déjà plus faible que ZFC, mais je ne suis pas un logicien). Nous pouvons déjà commencer à exprimer des théorèmes qui ne sont pas accessibles à NP par des quantificateurs alternés.

Ma question est de savoir s'il existe un moyen simple et connu de «dérouler» les quantificateurs dans les énoncés propositionnels d'ordre supérieur de sorte que les PCP pour les théorèmes de NP s'appliquent également à n'importe quel niveau de PH. Il est possible que cela ne soit pas possible - que le déroulement d'un quantificateur coûte, dans le pire des cas, une partie constante de la solidité ou de l'exactitude de notre système de preuve.

lo.logic pcp polynomial-hierarchy Ross Snider
la source

Il me semble qu'un PCP pour un problème pose presque par définition le problème dans BPP, ce qui voudrait dire qu'il est dans de Sipser – Gács – Lautemann. Mais peut-être aussi voir cette question connexe .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor,

Cela semble raisonnable, mais je suis confus. Si c'était vrai, cela ne mettrait-il pas NP dans BPP?

Ross Snider

Oops. J'aurais dû dire MA, qui est également contenu dans .

Σ_{2} \cap Π_{2}

$\Sigma_2 \cap \Pi_2$

Peter Shor

cela ne fonctionnera pas. le PH est résistant aux lemmes impliqués. considérez quelque chose comme EXP ^ 2. Il peut gérer RP, RNP, etc. comme une blague. Vous ne remontez pas facilement cette hiérarchie.

Steve Uurtamo

Réponses:

La vérité d'une déclaration est différente de celle d'avoir une (courte) preuve dans un système de preuve. Le langage est expressif mais cela ne signifie pas que toutes les déclarations valides dans le langage ont de courtes preuves dans le système.

Le théorème ne dit pas que vous pouvez vérifier la vérité d'une déclaration ou même l'exactitude d'une preuve arbitraire longue ou de théorèmes arbitraires. C'est pour les preuves d'appartenance à un ensemble , qui ont par définition des preuves d'appartenance de taille polynomiale (certificats). Le théorème dit seulement que vous n'avez pas besoin de lire la preuve complète (taille polynomiale) d'appartenance à un ensemble pour décider de son exactitude. $\mathsf{NP}$ $\mathsf{NP}$

Une implication du théorème est de l'appliquer à l'ensemble des théorèmes dans un langage arbitraire qui ont des preuves courtes (c'est-à-dire un polynôme arbitraire) dans un système de preuve efficace (c'est-à-dire qu'il est décidable en temps polynomial si une chaîne donnée est une preuve d'une donnée déclaration). Par exemple, les théorèmes de ZFC qui ont des preuves de taille où est la taille de la formule. Si le système de preuve est solide, vous pouvez vérifier de manière probabiliste l'exactitude des théorèmes qui ont des preuves courtes en lisant une petite partie de leurs preuves. Je pense que c'est le sens voulu de la déclaration informelle "les preuves rédigées dans un langage mathématique strict peuvent être vérifiées efficacement à tout degré d'exactitude souhaité sans avoir à lire l'intégralité de la preuve ". $n^{100}$ $n$

Kaveh
la source

Permettez-moi d'essayer de clarifier.

Considérez le problème de calcul suivant: étant donné une déclaration mathématique (dans votre système d'axiomes préféré) et un nombre n donné en représentation unaire, décidez si la déclaration a une preuve de taille n.

C'est un problème NP: étant donné une preuve, on peut vérifier efficacement qu'il est de taille n et qu'il s'agit d'une preuve valide du théorème. Remarque: même si l'instruction implique des quantificateurs comme FOR ALL, cela ne signifie pas que le vérificateur doit vérifier toutes les possibilités, cela signifie simplement que le vérificateur utilise des règles d'inférence qui impliquent le quantificateur FOR ALL.

Le théorème PCP s'applique donc à ce problème, et il existe donc un format de preuve (différent) qui permet une vérification probabiliste.

Autre remarque (concernant la remarque de Peter): Le vérificateur PCP utilise uniquement l'aléatoire logarithmique. Cela signifie qu'il pourrait être remplacé par un vérificateur standard, déterministe, qui examine l'ensemble de la preuve. C'est avoir un vérificateur PCP pour une langue qui le met dans NP.

Dana Moshkovitz
la source