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) |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, | + | Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$. Für sublinearen Speicherverbrauch vereinbart man, dass die Eingabe in einem eigenen Read-Only-Band übergeben wird, da dieser einem ansonsten schon linear viel zusätzlichen Speicherplatz brächte. |
== 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]] | ||
Aktuelle Version vom 29. August 2018, 21:17 Uhr
Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$. Für sublinearen Speicherverbrauch vereinbart man, dass die Eingabe in einem eigenen Read-Only-Band übergeben wird, da dieser einem ansonsten schon linear viel zusätzlichen Speicherplatz brächte.
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,
