NP-Vollständigkeit
Einfache Sprache
NP-vollständig sind die Probleme die gleichzeitig zu Klasse NP und NP-Schwer gehören. Also Probleme aus NP auf welche jedes andere Problem aus NP durch Polynomialzeitreduktion reduziert werden kann.
Def. NP-Vollständing
Eine Sprache $L_0$ heißt NP-vollständig g.d.w. $L_0\in \mathbf{NP}$ und $\forall L\in \mathbf{NP}$ gilt: $L\leq_\mathrm{p} L_0$ .
Bemerke: Wenn ein NP-vollständiges Entscheidungsproblem in P liegt, dann sind alle NP Entscheidungsproblem in P.