# Komplexitätstheorie

## SAT

## 3-SAT

## Clique

**Eingabe:** Ein ungerichteter Graph G = (V,E) und ein k ∈ N0 mit k ≤ |V |.
**Frage:** Existiert in G eine Clique der Größe mindestens k, d.h., eine Menge C ⊆ V mit |C| ≥ k, deren Knoten paarweise in G benachbart sind ?
Clique ist in NP:
**Zertifikat:** eine Menge C ⊆ V der Größe k
**Verifikation:** Überprüfung, dass alle Knoten in C paarweise benachbart sind

## Subset Sum

**Eingabe:** n Zahlen S = a1, . . . , an ∈ N0 und eine ”Teilsummenzahl“ b ∈ N0

**Frage:** Gibt es eine Menge I ⊆ {1, . . . , n}, so dass Pi∈I ai = b ? SUBSETSUM ist in NP

**Zertifikat:** eine Menge I ⊆ {1, . . . , n}

**Verifikation:** ¨Uberprüfung, dass die Zahlen ai mit i ∈ I sich genau zum Wert b aufaddieren

## Vertex Cover

**Eingabe:** Ein ungerichteter Graph G = (V,E) und eine natürliche Zahl
k ≤ |V |
**Frage:** Existiert in G ein ”Vertex Cover (Knoten¨uberdeckungsmenge)“ der
Größe höchstens k, d.h., eine Menge C ⊆ V mit |C| ≤ k, die von jeder
Kante aus E mindestens einen Randknoten enthält ?
VERTEXCOVER ist in NP.
**Zertifikat:** eine Menge C ⊆ V der Größe k (oder kleiner)
**Verifikation:** Überprüfung, dass jede Kante in E mindestens einen Randknoten in C besitzt

## Knapsack

## Partition

**Eingabe:** n Zahlen a1, . . . , an ∈ N0
**Frage:** Kann man diese Zahlen in zwei gleichgroße Teilsummen zerlegen, d.h., existiert eine Teilmenge I ⊆ {1, . . . , n}, so dass Pi∈I ai = Pj /∈I aj ?
PARTITION ist in NP.
**Zertifikat:** eine Menge I ⊆ {1, . . . , n}
**Verifikation:** Überprüfung, dass die Summe der Zahlen ai mit i ∈ I denselben Wert liefert wie die Summe der restlichen Zahlen

## TSP

###