Теорема Сэвича (1970):
NSPACE(f(n)) ⊆ DSPACE(f²(n)).
То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти.
Следствия PSPACE = NPSPACE NL ⊆ L²
Практическое применение
Одним из примеров практического применения Теоремы Сэвича является технология “Space-time tradeoff” - "выбор оптимального соотношения памяти и времени".
Литература
Section 8.1: Savitch’s Theorem, pp. 279–281. 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
Категория:Классы сложности