L: Unterschied zwischen den Versionen

Aus Einführung in die Theoretische Informatik und in die Mathematische Logik
Wechseln zu: Navigation, Suche
(Beispiele)
 
Zeile 1: Zeile 1:
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).
+
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 ==

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,