Теорема Сэвича
Материал из Википедии — свободной энциклопедии
Теорема Сэвича (1970):
- NSPACE(f(n)) ⊆ DSPACE(f²(n)).
То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать, за квадрат памяти.
[править] Следствия
[править] Литература
- Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN ISBN 0-534-94728-X Section 8.1: Savitch's Theorem, pp.279–281.
- Computational Complexity. — 1st edition. — Addison Wesley, 1993. — ISBN ISBN 0-201-53082-1 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