# Notizen 7

**P**
Die Menge aller polynommiell zeitbeschränkten deterministischen Turingmaschinen.

**NP**
Die Menge aller polynommiell zeitbeschränkten deterministischen Turingmaschinen.

Es gilt $P\subseteq NP$.

Zum Beweisen von $L\in P$ müssen wir eine passende Turingmaschine angeben.

Zum Beweisen von $L\in NP$ müssen wir nur einen passenden Verifikator angeben.

Ein Verifikator $V_L$ zur Sprache $L$ akzeptiert eine gültige Eingabe in $L$: $w$, und einen Beweis(Zertifikat) $c$.