Satz NP-vollständig durch Reduktion von NP-vollständig

Einfache Sprache

Dieser Satz hilft einem die NP-Vollständigkeit einer Sprache zu beweise ohne für alle möglichen Sprachen argumentieren zu müssen. Dazu wird von einem bekannten NP-vollständigem Problem auf das neue reduziert.

Def. Satz NP-vollständig durch Reduktion von NP-vollständig

Wenn $B$ NP-vollständig ist, $C\in$ NP und $B$ mit einer Polynomialzeitreduktion auf $C$ reduzierbar ist, dann ist $C$ NP-vollständig.

Beweis: Wir haben gegeben das $C\in\mathbf{NP}$. Damit müssen wir nach der Definition von NP-Vollständigkeit nur noch zeigen das jede Sprache $A\in\mathbf{NP}$ polynomial reduzierbar auf $C$ ist. Da wir wissen das $B$ NP-vollständig ist, ist $A$ polynomial reduzierbar auf $B$. $B$ ist wiederum polynomial reduzierbar auf $C$. Da Polynomialzeitreduktion sich verknüpfen lassen, ist $A$ polynomial reduzierbar auf $C$. Also ist $C$ NP-vollständig.