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 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)$

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

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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 … Deutsch Wikipedia
List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… … 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