WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

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

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

Следствия

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

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

Литература

  • Michael Sipser. Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN ISBN 0-534-94728-X. Section 8.1: Savitch’s Theorem, pp.279-281.
  • Christos Papadimitriou. 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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии