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) |
||
| 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$. | ||
| + | |||
| + | '''Lemma:''' $NL \subseteq P$. | ||
| + | |||
| + | '''Beweis:''' '''TODO''' | ||
| + | |||
== Beispiele == | == Beispiele == | ||
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 24. August 2018, 16:35 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$.
Lemma: $NL \subseteq P$.
Beweis: TODO
