Теорема Сэвича

Теорема Сэвича (1970):

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти.

Следствия

PSPACE = NPSPACE
NL ⊆ L²

Практическое применение

Одним из примеров практического применения Теоремы Сэвича является технология “Space-time tradeoff” - "выбор оптимального соотношения памяти и времени".

Литература

Michael Sipser Introduction to the Theory of Computation (англ.). — PWS Publishing, 1997. Section 8.1: Savitch’s Theorem, pp.279-281.
Christos Papadimitriou. Computational Complexity (неопр.). — 1st edition. — Addison Wesley, 1993. Pages 149—150 of section 7.3: The Reachability Method.
W.J.Savitch, «Relationship between nondeterministic and deterministic tape classes», J.CSS, 4, pp 177—192, 1970

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.