Satz 3SAT ist NP-vollständig

SAT 3SAT ist NP-vollständig

Einfache Sprache

Def. SAT 3SAT ist NP-vollständig

3SAT ist NP-vollständig.

Beweis: Offensichtlich ist $\mathrm{3SAT}\in\mathbf{NP}$. Daher müssen wir nach der Definition von NP-Vollständigkeit nur noch zeigen das jede Sprache in $\mathbf{NP}$ polynomial reduzierbar auf $\mathrm{3SAT}$ ist. Dazu benutzen wir den Satz NP-vollständig durch Reduktion von NP-vollständig um von der NP-Vollständigkeit von SAT auf die NP-Vollständigkeit von $\mathrm{3SAT}$ zu schließen.