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:

Lemma: $NL \subseteq P$.

Beweis: TODO