L: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil…“) |
Css (Diskussion | Beiträge) (→Beispiele) |
||
| Zeile 2: | Zeile 2: | ||
== Beispiele == | == Beispiele == | ||
| + | |||
| + | === k-Cliquen in Graphen === | ||
| + | |||
| + | Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz. | ||
=== Erreichbarkeit in Graphen === | === Erreichbarkeit in Graphen === | ||
| − | + | Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang, | |
| − | |||
[[Kategorie:TODO]] | [[Kategorie:TODO]] | ||
Version vom 29. August 2018, 17:22 Uhr
Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil es sonst nicht möglich ist, weniger als linear viel Speicher zu brauchen).
Beispiele
k-Cliquen in Graphen
Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz.
Erreichbarkeit in Graphen
Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang,
