Satz CLIQUE is NP-vollständig

Einfache Sprache

Def. Satz CLIQUE is NP-vollständig

CLIQUE ist NP-vollständig.

Idee:

Beweis: Wir zeigen zunächst das $\mathrm{CLIQUE}\in \mathbf{NP}$. Dazu geben wir einen Polynomieller Verifizierer $V$ an der für die Eingabe $\langle\langle G,k\rangle, c\rangle$ wie folgt funktioniert:

1. Prüfe ob $c$ eine Teilgraph von $G$ ist mit $k$ Knoten.
2. Prüfe ob $G$ für alle zwei Knoten aus $c$ die Kante hat.
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 G,k\rangle$ wie folgt funktioniert:
4. Wähle nichtdeterministisch eine Teilmenge $c\subseteq G$ der Größe $k$.
5. Prüfe ob $G$ für alle zwei Knoten aus $c$ die Kante hat.
6. Falls ja accept, sonst reject

Nun müssen wir noch zeigen das jede Sprache in NP polynomial reduzierbar auf $\mathrm{CLIQUE}$ ist. Dazu nutzen wir den Satz NP-vollständig durch Reduktion von NP-vollständig, den Satz 3SAT is poly reduzierbar auf CLIQUE und den Satz 3SAT ist NP-vollständig. Es folgt logisch das