Satz von Savitch

Satz von Savitch

Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke gelöst werden kann.

Eine Folgerung aus dem Satz von Savitch ist die Gleichheit von PSPACE und NPSPACE.

Formale Definition

Sei s:\mathbb{N}\rightarrow\mathbb{N} eine bandkonstruierbare Funktion mit s(n)\geq\log(n). Dann gilt:

\text{NSPACE}(s(n)) \subseteq \text{DSPACE}((s(n))^2)

Literatur

  • Walter Savitch: Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4(2):177-192, 1970.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Theorem von Savitch — Der Satz von Savitch oder Theorem von Savitch ist ein Satz aus der Komplexitätstheorie, der 1970 von Walter Savitch bewiesen wurde. Er besagt, dass ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares …   Deutsch Wikipedia

  • Savitch — Walter Savitch ist emeritierter Professor für Informatik an der University of California, San Diego. Savitch ist vor allem dafür bekannt, dass er die Komplexitätsklasse NL der nichtdeterministisch logarithmischen Probleme definiert hat, und… …   Deutsch Wikipedia

  • Walter Savitch — (* 21. Februar 1943) ist emeritierter Professor für Informatik an der University of California, San Diego. Savitch erwarb 1969 an der University of California, Berkeley den Ph.D. Grad in Mathematik. Er ist vor allem dafür bekannt, dass er die… …   Deutsch Wikipedia

  • Liste von Sätzen der Informatik — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z C Satz von Cook: Es existiert eine Teilmenge von …   Deutsch Wikipedia

  • Aufwandsklasse — Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine Komplexitätsklasse durch eine obere Schranke für… …   Deutsch Wikipedia

  • Aufwandsklassen — Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine Komplexitätsklasse durch eine obere Schranke für… …   Deutsch Wikipedia

  • Stephen A. Cook — 2008 Stephen Arthur Cook (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada. Sein Hauptbetätigungsfeld ist die Komplexitätstheorie; Cook arbeitet neben seiner Lehrtätigkeit aber auch an… …   Deutsch Wikipedia

  • NL-Vollständigkeit — In der Komplexitätstheorie bezeichnet NL die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können. NL ist eine Erweiterung der Klasse L, die analog für… …   Deutsch Wikipedia

  • NLOGSPACE — In der Komplexitätstheorie bezeichnet NL die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können. NL ist eine Erweiterung der Klasse L, die analog für… …   Deutsch Wikipedia

  • STCON — Das Erreichbarkeitsproblem in Graphen (auch STCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt. Existiert solch ein Weg, so ist t von s aus erreichbar. Andernfalls ist t… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”