Unterabschnitte
Eine Sprache
heißt NP-hart, falls für alle Sprachen
gilt:
Eine Sprache
heißt NP-vollständig (
), falls sie NP-hart ist und
.
- Sobald für ein NPC-Problem ein deterministischer Polynomialzeitalgorithmus angegeben werden kann, liegen wegen der NP-Härte alle Probleme aus NP in P!
- Die NP-Härte eines Problems kann nachgewiesen werden, indem man ein schon bewiesenes NP-hartes Problem auf dieses Problem reduziert. Die NP-Vollständigkeit kann somit nachgewiesen werden, indem man einen nichtdeterministisches Polynomialzeitalgorithmus findet (Guess-and-Check-Methode) und die NP-Härte dann nachweist.