Satz NP gdw. NDTM

Einfache Sprache

Def. Satz NP gdw. NDTM

Eine Sprache $L$ ist in NP g.d.w. $L$ durch eine NDTM in Polynomialzeit entschieden wird.

Idee

Wir müssen zeigen, dass wir einen Verifizierer in eine NDTM umwandeln können, und umgekehrt. Dazu simuliert eine NDTM den Verifizierer indem es das Zertifikat errät. Der Verifizierer simuliert eine NDTM indem der eine akzeptierende Berechnung als Zertifikat verwendet wird.

Beweis

“$\Rightarrow$”: Sei $A\in \mathbf{NP}$. Dann existiert nach dieser Definition von NP ein Polynomialzeit Verifizierer $V$ für $A$. Nehme an $V$ ist eine DTM mit einer Laufzeit von $n^k$ (hier ist $n$ die länge der Eingabe und $k$ eine beliebige Konstante). Dann konstruieren wir die NDTM $N$, die $A$ entscheidet und auf der Eingabe $w$ mit $n = |w|$ arbeitet, wie folgt:

1. Wähle nichtdeterministisch eine Zeichenkette $c$ mit höchstens der Länge $n^k$ aus.
2. Lass $V$ für die Eingabe $\langle w,c\rangle$ laufen.
3. Falls $V$ akzeptiere, dann accept, sonst reject.

“$\Leftarrow$”: Sei $N$ eine NDTM die in Polynomialzeit läuft und $A$ entscheidet. Dann konstruiere den Verifizierer $V$ der die Eingabe $\langle w,c\rangle$ erwartet, wobei $w$ und $c$ zwei Zeichenketten sind, wie folgt:

1. Simuliere $N$ auf der Eingabe $w$. Dabei interpretieren wir die einzelnen Symbole in $c$ als die nichtdeterministischen Entscheidungen die in den verschiedenen Schritten der Berechnung gefällt werden müssen.
2. Falls die Berechnung akzeptiert, accept, sonst reject.