Aperçu

1

La classe P est la classe des problèmes qui peuvent être décidés en temps polynomial par une machine de Turing déterministe, et la classe NP est la classe des problèmes pour lesquels, étant donné une preuve (appelée Témoin ou Witness) que la réponse est Oui, la validité du Témoin peut être jugée (cela s'appelle la vérification) en temps polynomial. Étant donné que les problèmes décidables en temps polynomial peuvent être vérifiés en temps polynomial, il est évident que P⊆NP, mais il n'est pas clair si P est un sous-ensemble propre de NP. Il n'y a pas encore de preuve, mais de nombreux chercheurs pensent que P≠NP. La conjecture selon laquelle la classe P et la classe NP ne sont pas égales est appelée la "Conjecture P≠NP".