Beispiele für NPC

Es gibt NP-vollständige Probleme:

• das Wortproblem für NP-Maschinen
• SAT (Erfüllbarkeit aussagenlogischer Formeln)
• 3SAT (...in konjunktiver Normalform mit je 3 Literalen pro Klausel)
• Vertex Cover, ...

Beweis: das erste folgt (fast direkt) aus Definition, die anderen durch Reduktionen, denn:

Satz: wenn A $\in$ NPC und A$\le_{P}^{}$B, dann B $\in$ NPC.