Si la vérification de la solution d'un problème est dans P (polynomiale) alors sa résolution est dans NP (car il peut être résolu dans P par un machine non déterministe d'où le nom NP) ; ça c'est la définition de NP.
Pour être précis, c'en est une caractérisation. La définition originale concerne les machines Non déterministes (d'où le N).
[^] # Re: Des commentaires de chercheur ?
Posté par lenod . En réponse au journal P=NP démontré ?. Évalué à 1.
Pour être précis, c'en est une caractérisation. La définition originale concerne les machines Non déterministes (d'où le N).