#001 / 100•Space, Chance & Computation•MathTCG #401 / 500•✦✦✦✦✦✦Mythique•∀Logique•Concept

Problème P contre NP

Période historique : 1971

La grande énigme du millénaire : tout problème dont la solution est vérifiable efficacement peut-il être résolu efficacement ?

Contenu & Formulation mathématique

Définition rigoureuse

La grande énigme du millénaire : tout problème dont la solution est vérifiable efficacement peut-il être résolu efficacement ?

\mathbf{P} \stackrel{?}{=} \mathbf{NP}, \quad \mathbf{P} = \bigcup_{k=1}^{\infty} \mathbf{TIME}(n^k), \quad \mathbf{NP} = \bigcup_{k=1}^{\infty} \mathbf{NTIME}(n^k)

Genèse & Portée historique

Formulé par Stephen Cook et Leonid Levin en 1971, le problème P versus NP demande si la classe P des problèmes résolubles en temps polynomial coïncide avec la classe NP des problèmes dont une solution postulée est vérifiable en temps polynomial. Doté d'un prix d'un million de dollars par l'Institut Clay, il s'agit de la question la plus profonde et conséquente de l'informatique théorique et de la logique moderne.

Kurt Gödel en avait déjà pressenti l'importance dans une lettre historique adressée à John von Neumann en 1956, s'interrogeant sur le nombre de pas nécessaires à une machine pour prouver un théorème mathématique de longueur n.

« Si trouver une vérité était aussi aisé que de la contempler, l'esprit humain n'aurait plus de mystère à conquérir. »