Se un problema X è in C e difficile per C, allora X si dice che X è completo per C. Ciò significa che X è il problema più difficile in C. Poichè molti problemi potrebbero essere altrettanto gravi, si potrebbe dire che X è uno dei problemi più gravi in C.) Così la classe di problemi NP-completa contiene i problemi più difficili in NP, nel senso che sono quelli più probabili non essere in P. Perchè il problema P = N Ciò è dovuto al fatto che una soluzione polinomio tempo-polinomiale a? 1 darebbe una soluzione polinomiale tempo-polinomiale a. 2. Allo stesso modo, poichè tutti i problemi NP possono essere ridotti al set, trovare un problema NP-completo che può essere risolto nel tempo polinomiale significherebbe che P = NP.
NP completa problemi contengono la più bassa probabilità di essere situato in quale classe di problema?
NP P P