Меню Главная Случайная статья Настройки Теорема Сэвича Материал из https://ru.wikipedia.org Теорема Сэвича (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. W.J.Savitch, «Relationship between nondeterministic and deterministic tape classes», J.CSS, 4, pp 177–192, 1970