NP-Schwer

Einfache Sprache

NP-schwer ist die Eigenschaft eines Problems, mindestens so schwer lösbar zu sein wie alle Probleme aus NP. Für alle Probleme aus NP muss es also eine Polynomialzeitreduktion geben welche es in die Sprache des NP-schweren Problem umwandelt.

Def. NP-Schwer

Eine Sprache $L_0$ heißt NP-schwer, g.d.w.

$$\forall L \in \mathbf{NP} : L \leq_\mathrm{P} L_0\;.$$