Raumkomplexität

Das Raumkomplexität von einem Algorithmus oder ein Computer Programm ist die Menge an Speicherraum, die erforderlich ist, um eine Instanz der zu lösen Rechenproblem als Funktion der Eigenschaften der Eingabe. Es ist der Speicher, der von einem Algorithmus benötigt wird, bis er vollständig ausgeführt wird.[1]

Ähnlich zu Zeitkomplexität, die Raumkomplexität wird oft asymptotisch in exprimiert Big O Notation, wie zum Beispiel usw., wo n ist ein Merkmal der Eingabe, die die Raumkomplexität beeinflusst.

Raumkomplexitätsklassen

Analog zu Zeitkomplexitätsklassen Time (f (n)) und Ntime (f (n)), die Komplexitätsklassen DSpace (f (n)) und Nspace (f (n)) sind die Sätze von Sprachen, die durch deterministisch (jeweils nicht deterministisch) entschlossen werden können Turing -Maschinen diese Verwendung Platz. Die Komplexitätsklassen PSPACE und Npspace ermöglichen Polynom sein, analog zu P und Np. Das ist,

und

Beziehungen zwischen Klassen

Das Raumhierarchie Theorem erklärt das für alle Platzkonstruktionierbare Funktionen Es gibt ein Problem, das von einer Maschine mit gelöst werden kann Speicherraum, kann aber nicht von einer Maschine mit asymptotisch weniger gelöst werden als Platz.

Die folgenden Containments zwischen Komplexitätsklassen halten.[2]

Außerdem, Savitchs Theorem gibt die umgekehrte Eindämmung, die wenn Anwesend

Als direkte Folgerung, . Dieses Ergebnis ist überraschend, da es darauf hindeutet, dass der Nichtdeterminismus den Raum verringern kann, der erforderlich ist, um ein Problem nur um eine geringe Menge zu lösen. Dagegen die Exponentialzeithypothese Vermutungen, dass es für die Zeitkomplexität eine exponentielle Lücke zwischen deterministischer und nicht deterministischer Komplexität geben kann.

Das Imerman -Szelepcsényi Theorem gibt das wieder für an , ist unter Komplementation geschlossen. Dies zeigt einen weiteren qualitativen Unterschied zwischen Zeit- und Raumkomplexitätsklassen, da nicht deterministische Zeitkomplexitätsklassen unter Komplementation nicht geschlossen sind. Zum Beispiel wird vermutet, dass NP ≠ Co-NP.[3][4]

Logspace

L oder logspace ist der Satz von Problem Speicherplatz in Bezug auf die Eingabegröße. Sogar ein einzelner Zähler, der das gesamte indizieren kann -biteingabe erfordert Raum, sodass Logspace -Algorithmen nur eine konstante Anzahl von Zählern oder andere Variablen ähnlicher Bitkomplexität beibehalten.

Logspace und andere sublineare Raumkomplexität sind nützlich, wenn große Daten verarbeitet werden, die nicht in das Computer passen können RAM. Sie sind mit dem verwandt mit Streaming -Algorithmen, aber nur einschränken, wie viel Speicher verwendet werden kann, während Streaming -Algorithmen weitere Einschränkungen für die Eingabe der Eingabe in den Algorithmus haben. Diese Klasse sieht auch im Gebiet von verwendet von Pseudorandomness und Derandomisierung, wo Forscher das offene Problem betrachten, ob L = Rl.[5][6]

Die entsprechende nicht deterministische Raumkomplexitätsklasse ist Nl.

Hilfsraumkomplexität

Der Begriff Hilfsraum bezieht sich auf einen anderen Raum als den, der durch die Eingabe verbraucht wird. Die Komplexität des Hilfsraums könnte offiziell in Bezug auf a definiert werden Turing Maschine mit einem separaten Eingabeband Dies kann nicht geschrieben, nur lesen und ein herkömmliches Arbeitsband, an das geschrieben werden kann. Die Hilfsraumkomplexität wird dann über das Arbeitsband definiert (und analysiert). Betrachten Sie zum Beispiel die Tiefe-First-Suche von a ausgeglichener binärer Baum mit Knoten: seine Hilfsraumkomplexität ist .

Verweise

  1. ^ Kuo, Weg; Zuo, Ming J. (2003), Optimale Modellierung von Zuverlässigkeit: Prinzipien und Anwendungen, John Wiley & Sons, p. 62, ISBN 9780471275459
  2. ^ Arora, Sanjeev; Barak, Boaz (2007), Rechenkomplexität: ein moderner Ansatz (PDF) (Draft Ed.), p. 76, ISBN 9780511804090
  3. ^ Immerman, Neil (1988),, "Nichtdeterministischer Raum ist unter Komplementation geschlossen" (PDF), Siam Journal über Computing, 17 (5): 935–938, doi:10.1137/0217058, HERR 0961049
  4. ^ Szelepcsényi, Róbert (1987), "Die Methode, nicht deterministische Automaten zu erzwingen", Bulletin der Eatcs, 33: 96–100
  5. ^ Nisan, Noam (1992), "Rl ⊆ Sc", Verfahren des 24. ACM -Symposiums über die Computertheorie (STOC '92), Victoria, British Columbia, Kanada, S. 619–623, doi:10.1145/129712.129772, S2CID 11651375.
  6. ^ Reingold, Omer; Trevisan, Luca; Vadhan, Salil (2006), "Pseudorandom geht auf reguläre Digraphen und das Problem von RL vs. L." (PDF), STOC'06: Verfahren des 38. jährlichen ACM -Symposiums über die Theorie des Computers, New York: ACM, S. 457–466, doi:10.1145/1132516.1132583, HERR 2277171, S2CID 17360260