Complexité de la preuve d'une preuve ou non de P = NP

Y a-t-il eu des recherches sur la complexité de la preuve d'une résolution du problème P = NP? Sinon, étant donné le manque de progrès sur le problème, serait-il déraisonnable de supposer que toute preuve qui résout le problème P = NP nécessitera un nombre d'étapes super-polynomial?

Il est connu que toute preuve de limites inférieures de circuit super-polynomial (qui sont des déclarations légèrement plus fortes que ) nécessite des preuves de taille super-polynomiale, même exponentielle dans des systèmes de preuve faibles comme la résolution. Généraliser cela à des systèmes de preuve plus solides est un problème ouvert bien connu.$P\neq NP$

Voir la section 5 de cette enquête par A. Razborov où ces choses sont montrées.

La complexité de la preuve n'a de sens que lorsqu'il existe une séquence d'instructions dépendant d'un paramètre . Par exemple, la proposition indique (de manière informelle) qu'il n'y a pas de bijection . Cette séquence de propositions est difficile pour certains systèmes de preuve propositionnelle.P H P n [ n + 1 ] → [ n $n$$\mathsf{PHP}_n$$[n+1] \to [n]$

L'instruction est une instruction unique, vous ne pouvez donc pas lui appliquer directement la complexité de la preuve. Cependant, la séquence d'instructions suivante a du sens, pour des fonctions particulières : "il n'y a pas de circuit de taille résolvant correctement SAT pour les instances de longueur ". Cela a été considéré dans la littérature, par exemple par Razborov (qui a considéré le réglage de la complexité de preuve uniforme, c'est-à-dire l'arithmétique bornée). s ( n ) s ( n ) $\mathsf{P} \neq \mathsf{NP}$$s(n)$$s(n)$$n$

Nous avons 3 cas:

• Il existe une preuve que . Ensuite, il existe un algorithme résolvant le problème "Émettre une preuve que P = N P " qui s'exécute en temps O ( 1 ) . Il code en dur la preuve dans la machine de Turing elle-même et l’émet. Il s'exécute en même temps, peu importe son entrée.$P = NP$$P=NP$$O(1)$

• De même, s'il existe une preuve que , alors on peut écrire un algorithme émettant cette preuve en temps O ( 1 ) .$P\neq NP$$O(1)$

• $O(\infty)$

Ce n'est pas parce que nous n'avons trouvé aucune preuve qu'elle n'existe pas et que les classes de complexité sont définies en fonction de ce qui existe.

$P=NP$

Ce que nous savons, c'est que, en général, le problème de «prendre une instruction dans la logique des prédicats et déterminer s'il y a une preuve» est indécidable. Il n'y a donc pas de procédures génériques de preuve dans lesquelles nous pouvons brancher P vs NP, qui sont garanties de produire un résultat.

Si P = NP, tout ce que vous avez à faire est de créer un algorithme de temps polynomial pour résoudre un problème NP-complet, et de prouver qu'il est bien polynomial (ce qui pourrait être difficile, par exemple, l'algorithme Simplex s'exécute généralement très rapidement mais prouve que ça tourne vite semble incroyablement difficile).

Ok, cela pourrait être très difficile. Supposons que nous trouvions un algorithme qui résout soi-disant le problème du voyageur de commerce dans O ( ). Dure. Nous ne pouvons même pas mesurer le temps d'exécution d'un problème avec deux villes.$n^{100}$