Unterabschnitte
Eine Sprache
![$K$](img234.png)
heißt NP-hart, falls für alle Sprachen
![$L\in NP$](img237.png)
gilt:
Eine Sprache
![$K$](img234.png)
heißt NP-vollständig (
![$K\in NPC$](img239.png)
), falls sie NP-hart ist und
![$K\in NP$](img240.png)
.
- 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.