Ψ Die Informatikseite

Menü
Unterabschnitte

NP-hart, NP-vollständig

NP-hart

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

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

NP-vollständig

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

Sätze

  • 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.