P est la classe des problèmes polynomiaux (en taille de l'entrée) sur une machine déterministe

NP est la classe des problèmes polynomiaux (en la taille de l'entrée) sur une machine NON déterministe.

P est l'enesemble des problèmes dont on peut trouver une solution facilement.

NP est l'ensemble des problèmes dont on peut vérifier une solution facilement.

PVC : statut inconnu (Problème voyageur de commerce)
Vérification PVC :
Données : un graphe (S,A), une borne et un circuit candidat
Question : Le circuit candidat a-t-il un coût inférieur ou égal à la borne ?

On a P < NP. A-t-on NP inclus P et donc P ?= NP (1 Million de Dollars en jeu :D)