Теорема Сэвича
Теорема (1970):
- NSPACE(f(n)) ⊆ (f²(n)).
То есть, если недетерминированная машина Тьюринга может решить проблему используя f(n) памяти, то детерминированная машина Тьюринга сможет это сделать за квадрат памяти.
Следствия
Практическое применение
- Одним из примеров практического применения Теоремы Сэвича является технология “Space-time tradeoff” - "выбор оптимального соотношения памяти и времени".
Литература
- [англ.]. 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
Эта статья слишком короткая. |
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Теорема Сэвича, Что такое Теорема Сэвича? Что означает Теорема Сэвича?
Teorema 1970 NSPACE f n f n To est esli nedeterminirovannaya mashina Tyuringa mozhet reshit problemu ispolzuya f n pamyati to determinirovannaya mashina Tyuringa smozhet eto sdelat za kvadrat pamyati SledstviyaPSPACE NPSPACE NL L Prakticheskoe primenenie Odnim iz primerov prakticheskogo primeneniya Teoremy Sevicha yavlyaetsya tehnologiya Space time tradeoff vybor optimalnogo sootnosheniya pamyati i vremeni Literatura angl Introduction to the Theory of Computation angl PWS Publishing 1997 Section 8 1 Savitch s Theorem pp 279 281 Christos Papadimitriou Computational Complexity neopr 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 1970Eta statya slishkom korotkaya Pozhalujsta dopolnite eyo eshyo hotya by neskolkimi predlozheniyami i uberite eto soobshenie Esli statya ostanetsya nedopisannoj ona mozhet byt vystavlena k udaleniyu Dlya ukazaniya na prodolzhayushuyusya rabotu nad statyoj ispolzujte shablon subst Redaktiruyu Administratoram i podvodyashim itogi eta pometka ostavlena 2010 06 10 Prosba ochen korotkie zagotovki statej ranee chem cherez dva dnya posle sozdaniya ne udalyat 10 iyunya 2010
