Ein Problem ist NP-vollständig, wenn es in NPNPNP liegt und jedes Problem aus NPNPNP in polynomieller Zeit darauf reduzierbar ist.
Findet man für ein NP-vollständiges Problem einen Polynomialzeit-Algorithmus, dann gilt P=NPP=NPP=NP.