P

P ist die Klasse der in polynomieller Zeit lösbaren Entscheidungsprobleme. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$. Die meisten praxisrelevanten Algorithmen liegen in $P$.

Beispielsweise sind QuickSort und MergeSort in $P$.

Lemma: $L \subseteq P$.

Beweis: Werde $K\in L$ von der Maschine $M$ entschieden, und beschränke $g\in{\cal O}(log)$ den Platzverbrauch. Für eine Eingabe $x$ brauchen wir also maximal $g(|x|)$ Speicherziellen. Nun gibt es aber maximal $|{\cal L}|^{g(|x|)}$ verschiedene Möglichkeiten, was auf diesem Band gespeichert sein kann. Aber da $g$ asymptotisch gleich zu $\log$ ist, muss $|{\cal L}|^{g(|x|)}\in{\cal O}(x^k)$ für ein $k$. Da man in einem Durchlauf höchstens alle möglichen Speicherbelegungen durchlaufen kann, ist damit die Laufzeit durch ein Polynom beschränkt.

Lemma: $NL \subseteq P$.

Beweis: Wir müssen nur alle möglichen Eingaben des Orakelbandes durchprobieren. Diese sind polynomiell viele, und wir können sie in polynomieller Zeit, wie eben gezeigt, überprüfen.