Réduction de P vs NP à SAT

La question suivante utilise des idées de cryptographie appliquées à la théorie de la complexité. Cela dit, il s'agit d'une question purement théorique, et aucune connaissance cryptographique n'est requise pour y répondre.

J'écris délibérément cette question de manière très informelle. Manquant de détails, il est peut-être mal énoncé. N'hésitez pas à signaler les corrections dans vos réponses.

Dans le journal suivant:
Cryptographie non malléable, Danny Dolev, Cynthia Dwork et Moni Naor, SIAM Rév.45, 727 (2003), DOI: 10.1137 / S0036144503429856 ,
les auteurs écrivent:

Supposons que le chercheur A ait obtenu une preuve que P ≠ NP et souhaite communiquer ce fait au professeur B. Supposons que, pour se protéger, A prouve sa prétention à B d'une manière à connaissance nulle ...

Il existe plusieurs problèmes NP-complets standard, comme la satisfiabilité (SAT), le graph-hamiltonicité et le graph-3-colorabilité (G3C), pour lesquels il existe des preuves de connaissance zéro. La manière standard de prouver un théorème NP est de le réduire d'abord à une instance des problèmes NP-complets susmentionnés, puis de réaliser la preuve de connaissance zéro.

Cette question concerne cette réduction. Supposons que le P vs NP soit réglé de l'une des manières suivantes:

• P = NP
• P ≠ NP
• P vs. NP est indépendant de la théorie des ensembles axiomatiques standard.

Soit σ la preuve. Ensuite, P vs. NP est dans un langage NP (car il existe une courte preuve pour cela). La réduction du théorème (disons P ≠ NP) au problème NP-complet (disons SAT) est indépendante de σ. C'est:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

C'est bien au-delà de mon imagination! Il semble que, même si on nous donne la preuve σ, il est peu probable que nous puissions construire une telle formule ϕ.

Quelqu'un pourrait-il nous éclairer là-dessus?

De plus, soit L un langage NP dans lequel se trouve P vs. NP . Le langage est composé d'une infinité de théorèmes comme P vs. NP , de tailles arbitraires.

Qu'est-ce qu'un candidat pour L?
L peut-il être NP-complet?

La façon de voir tester une instruction mathématique (par exemple, une résolution de P vs NP) comme une question de la forme "est la formule .. satisfaisable" est la suivante:

Correction d'un système d'axiome. Étant donné une chaîne de longueur n, que la chaîne soit une preuve de l'énoncé mathématique dans le système axiomatique, c'est quelque chose que l'on peut définir de manière simple: la chaîne doit être constituée de propositions. Chaque proposition doit être soit un axiome, soit suivre les propositions précédentes par l'une des règles d'inférence.

Ce n'est pas un problème de définir une formule booléenne qui vérifie tout cela. Tout ce que vous devez savoir, c'est la longueur n de l'épreuve!

P vs NP est dans NP (car il existe une courte preuve pour cela)

Cela n'a pas beaucoup de sens pour moi. NP est une classe de complexité pour les problèmes de décision qui ont des instances arbitrairement grandes, et P vs NP n'en a pas. D'après ce que vous dites plus tard:

soit L un langage NP dans lequel se trouve P vs. NP.

vous pouvez plutôt dire que P vs NP est une instance d'un problème NP; Mais bien sur! C'est aussi l'instance d'un nombre infini de problèmes P, DTIME (n), etc. En particulier, voici deux candidats DTIME (1) pour L, dont l'un précisément est correct: toujours revenir true; ou toujours revenir false.