Satz Hamiltonwegproblem ist in NP

Einfache Sprache

Def. Satz Hamiltonwegproblem ist in NP

Wir definieren die NDTM $M$, die wie folgt für die Eingabe $\langle G, s, t\rangle$ von HAMPATH funktioniert:

1. Schreibe eine Liste mit $m$ Zahlen, $p_1,\ldots,p_m$, mit $m = |V|$. Jede Zahl wird nichtdeterministisch ausgewählt zwischen $1$ und $m$.
2. Falls die Liste Wiederholungen enthält, reject.
3. Falls $s\not=p_1$ oder $t\not=p_m$, reject.
4. Für jedes $i$ zwischen $1$ und $m-1$ prüfe ob $(p_i,p_{i+1})\in G$. Falls nicht reject.
5. Sonst accept.

Alle Schritte von $M$ laufen offensichtlich in nichtdeterministisch polynomielle Zeit. Also ist $\mathrm{HAMPATH}\in \mathbf{NP}$.