Theoretische Informatik - NP-hart, NP-vollständig

Nächste Seite: Aussagelogik Aufwärts: NPC Beweise Vorherige Seite: Polynomielle Reduzierbarkeit Inhalt

Unterabschnitte

NP-hart, NP-vollständig

Eine Sprache

heißt NP-hart, falls für alle Sprachen $L\in NP$ gilt:

$\begin{displaymath}L\leq_{poly}K\end{displaymath}$

Eine Sprache

heißt NP-vollständig ( $K\in NPC$ ), falls sie NP-hart ist und $K\in NP$ .

Sobald für ein NPC-Problem ein deterministischer Polynomialzeitalgorithmus angegeben werden kann, liegen wegen der NP-Härte alle Probleme aus NP in P!

$\begin{displaymath}NP=P \end{displaymath}$
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.