P: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „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 meiste…“) |
Css (Diskussion | Beiträge) |
||
| (4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| 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:''' 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. | ||
Aktuelle Version vom 29. August 2018, 21:25 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: 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.
