Problème P = NP - Définition

Indécidabilité de P=NP

Le fait qu'il soit très difficile de trouver une démonstration à P = NP ou P ≠ NP peut amener à envisager que ce problème est indécidable. Un problème indécidable est un problème dont la vérité ou la fausseté n'admet aucune démonstration dans un système formel donné. Dit autrement, la vérité ou la fausseté sont toutes deux compatibles et cohérentes avec le système formel. On parle alors d'indépendance du problème par rapport au système formel. Il est alors possible de prendre librement la vérité ou bien la fausseté du problème comme nouvel axiome et l'ajouter aux axiomes du système formel pour forger un nouveau système formel. L'existence de telles propositions a été démontrée par Gödel en 1931 par le célèbre théorème d'incomplétude de Gödel.

Pendant longtemps, on a pensé que l'indécidabilité était réservée à des problèmes artificiels, spécialement conçus pour être indécidables. Cependant, depuis que l'hypothèse du continu a été démontrée indécidable par rapport au système formel ZFC en 1963, on sait que des problèmes mathématiques importants et fondamentaux peuvent être indécidables, et dont la vérité ou la fausseté ne peut être établie.

Il n'est donc pas exclu que le problème P = NP soit indécidable, et que toute démonstration en soit impossible dans le système formel ZFC utilisé par les mathématiciens. Un certain nombre de résultats viennent étayer cette possibilité, bien que la communauté des théoriciens pense en général que ce problème n'est pas indécidable (et continue par conséquent à en recherche activement une démonstration).

Résultats en faveur de l'indécidabilité

R. DeMillo et R. Lipton on démontré en 1979 que dans un certain système formel nommé EF, moins puissant que ZFC, mais suffisament puissant pour démontrer beaucoup de problèmes mathématiques, le problème P = NP était indécidable. Malheureusement, EF a été artificiellement construit, et trop faible pour en tirer des conclusions significatives. Toutefois, ce résultat vient confirmer que, pour démontrer ce problème, il faudra mettre en oeuvre des techniques de démonstrations inhabituelles, qui ne peuvent être employées dans EF.

Autre résultat : en théorie de la complexité algorithmique, on utilise la notion d'Oracle pour étudier un problème en s'affranchissant d'une autre problématique, considérée comme extérieure au problème étudié. Par hypothèse, un Oracle saura répondre à un problème déterminé (par exemple, un nombre est-il premier ou non, ou bien le problème de l'arrêt) instantanément. Pour chaque Oracle, il existe les classes de complexité P_O,NP_O, etc.. correspondantes aux problèmes qui peuvent être résolus ou vérifiés en temps polynomial, à l'aide de cet Oracle.

Avec certains Oracles, on peut prouver que P_O = NP_O, et avec d'autres que P_O ≠ NP_O. C'est un résultat auquel on peut s'attendre si le problème P = NP est indécidable, car toute preuve du problème sans Oracle devra pouvoir s'adapter aux cas avec Oracle et donner ces deux résultats différents, ce qui est a priori très difficile, voire impossible. De plus, il a été prouvé que le problème Erreur est indécidable avec certains Oracles, dans ZFC, ce qui est considéré comme significatif en faveur de l'indécidabilité du problème.