Satz SUBSET-SUM is NP-vollständig

Einfache Sprache

Def. Satz SUBSET-SUM is NP-vollständig

SUBSET-SUM ist NP-vollständig.

Idee:

Beweis: Wir zeigen zunächst das $\text{SUBSET-SUM}\in \mathbf{NP}$. Dazu geben wir einen Polynomieller Verifizierer $V$ an der für die Eingabe $\langle\langle S,t\rangle, c\rangle$ wie folgt funktioniert:

1. Prüfe ob $c$ eine Menge von Zahlen ist mit der Summe $t$.
2. Prüfe ob $S$ alle Zahlen aus $c$ beinhaltet.
3. Falls beides stimmt, accept, sonst reject. Alternativ kann kann dies auch nach Satz NP gdw. NDTM eine NDTM die in Polynomialzeit läuft gezeigt werden. Also sei $N$ eine NDTM die für die Eingabe $\langle S,t\rangle$ wie folgt funktioniert:
4. Wähle nichtdeterministisch eine Teilmenge $c\subseteq S$.
5. Prüfe ob die Summe der Zahlen in $c$ gleich $t$ ist.
6. Falls ja accept, sonst reject.