Definition NP-schwer und NP-vollständig
Satz 14 (NP-vollständig)
Satz 15 (NP und NP-Vollständigkeit)
Satz 16 (von Cook und Levin)
SAT ist NP-vollständig
Satz 17 (3SAT)
3SAT ist NP-vollständig
Formel in 3KNF (drei Variablen miteinander konjunkt)
Satz 18 (Clique)
CLIQUE ist NP-vollständig
Satz 19 (HAMPATH)
HAMPATH ist NP-vollständig
Satz 20 (HAMCIRC)
Hamcirc ist np-vollständig
Zuletzt geändertvor einem Jahr
