P: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) |
||
| Zeile 4: | Zeile 4: | ||
'''Lemma:''' $L \subseteq P$. | '''Lemma:''' $L \subseteq P$. | ||
| − | '''Beweis:''' | + | |
| + | '''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$. | '''Lemma:''' $NL \subseteq P$. | ||
Version vom 29. August 2018, 21:22 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: 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: TODO
