P: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
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$. | 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$. | '''Lemma:''' $NL \subseteq P$. | ||
Version vom 29. August 2018, 20:14 Uhr
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
