---
# System prepended metadata

title: $CLIQUE$

---

# $CLIQUE$
## $CLIQUE \in NP$
Wir konstruieren einen Polyzeit-Verifizierer. Sei $G$ ein Graph und $k$ eine Zahl. Wir beantworten nun, ob $(G,k) \in CLIQUE$. Dazu erhalten wir ein Zertifikat $y \in \{0,1\}^{|V(G)|}$, wobei jeweils eine $1$ an Stelle $i$ bedeutet, dass der $i$-te Knoten in der Clique liegen soll. Die daraus resultierende Teilmenge können wir trivial in $O(|V(G)|^2)$ auf Cliquenhaftigkeit überprüfen und ob sie genug Knoten hat.

Gibt es nun eine solche Clique, dann gibt es ein Zertifikat, sodass der Polyzeit-Verifizierer die Eingabe akzeptiert.

Gibt es Zertifikat, dann gibt es auch Clique, da es dann eine vollvernetzte Teilmenge von min $k$ Größe gibt, was eine Clique darstellt.

## $IS \le_P CLIQUE$
aoeu