Персональные инструменты
 

NTIME — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Класс ''NTIME(t(n))'', означает класс задач,
+
#REDIRECT [[discopal:{{PAGENAME}}]]
разрешимых на [[Недетерминированная машина Тьюринга|недетерминированной машине Тьюринга]] за время ''t(n)''.
+
 
+
Более формально:
+
Язык <amsmath>L \subset \Sigma^*</amsmath> принадлежит классу <amsmath>{\cal DTIME}(t(n))</amsmath>,
+
если существует [[недетерминированная машина Тьюринга]] ''T'', разрешающая данный язык, и сложность ее работы в наихудшем случае, <amsmath>time_{T(n)} \leq t(n)</amsmath>, т.е. не превышает ''t(n)'', где ''n''-длина входного слова.
+
 
+
[[Category:Классы сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:39, 13 июня 2011

  1. REDIRECT discopal:NTIME