Reduktion, Vollständigkeit

Für Sprachen A und B:

A$\le_{P}^{}$B, falls es eine P-berechenbare Funktion f gibt. so daß $\forall$w : w $\in$ A$\iff$f (w) $\in$ B.

Satz: $\le_{P}^{}$ ist transitiv und reflexiv.

Satz: aus A$\le_{P}^{}$B und B $\in$ NP folgt A $\in$ NP.

B heißt NP-vollständig, falls

• B $\in$ NP und
• $\forall$A $\in$ NP : A$\le_{P}^{}$B

Die Klasse der NP-vollständigen Sprachen heißt NPC.