NSPACE

Im Computerkomplexitätstheorie, nicht deterministischer Raum oder Nspace ist der Rechenressource Beschreibung der Speicherraum Für ein Nichtdeterministische Turing-Maschine. Es ist das nicht deterministische Gegenstück von DSpace.

Komplexitätsklassen

Das Maß nspace wird verwendet, um die zu definieren Komplexitätsklasse deren Lösungen können durch a bestimmt werden Nichtdeterministische Turing-Maschine. Das Komplexitätsklasse Nspace (f(n)) ist der Satz von Entscheidungsprobleme das kann durch a gelöst werden Nichtdeterministische Turing-Maschine, M, mit Platz O(f(n)), wo n ist die Länge des Eingangs.[1]

Mehrere wichtige Komplexitätsklassen können in Bezug auf die Weise definiert werden Nspace. Diese beinhalten:

  • Regs = DSPACE (O(1)) = nspace (O(1)), wobei Reg die Klasse von ist reguläre Sprachen (Der Nichtdeterminismus fügt keine Macht im konstanten Raum hinzu).
  • Nl = Nspace (O(Protokolln))
  • CSL = Nspace (O(n)), wobei CSL die Klasse von ist Kontextsensitive Sprachen.
  • PSPACE = Npspace =
  • Expace = Nexpspace =

Das Imerman -Szelepcsényi Theorem Staaten, die nspace (s(n)) wird für jede Funktion unter Komplement geschlossen s(n) ≥ log n.

Eine weitere Verallgemeinerung ist Aspace, definiert mit Wechsel Turing -Maschinen.

Beziehung zu anderen Komplexitätsklassen

DSpace

Nspace ist das nicht deterministische Gegenstück von DSpace, die Klasse von Speicherraum auf einen deterministische Turing -Maschine. Zuerst per Definition, dann durch Savitchs Theorem, wir haben das:

Zeit

Nspace kann auch verwendet werden, um die zeitliche Komplexität von a zu bestimmen deterministische Turing -Maschine nach dem folgenden Satz:

Wenn eine Sprache L wird im Weltraum entschieden S(n) (wo S(n) ≥ log n) Durch ein nicht deterministisches TM gibt es dann eine Konstante C so dass L wird rechtzeitig entschieden O(CS(n)) durch eine deterministische.[2]

Einschränkungen

Das Maß von Raumkomplexität bezüglich DSpace ist nützlich, da es die Gesamtmenge an Speicher darstellt, die ein tatsächlicher Computer eingeben müsste Rechenproblem mit einem gegebenen Algorithmus. Der Grund ist, dass DSpace die von der Raumkomplexität verwendete Raumkomplexität beschreibt deterministische Turing -Maschinen, die tatsächliche Computer darstellen können. Andererseits beschreibt Nspace die Raumkomplexität von Nichtdeterministische Turing-Maschinen, die bei dem Versuch, tatsächliche Computer darzustellen, nicht nützlich sind. Aus diesem Grund ist Nspace in seiner Nützlichkeit für reale Anwendungen begrenzt.

Verweise

  1. ^ Sipser, Michael (2006). Einführung in die Theorie der Berechnung (2. Aufl.). Kurs Technologie. pp.303–304. ISBN 978-0-534-95097-2.
  2. ^ Goddard, Wayne (2008). Einführung der Berechnungstheorie. Jones und Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

Externe Links