WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

Новая страница

Класс ''NTIME(t(n))'', означает класс задач,
разрешимых на [[Недетерминированная машина Тьюринга|недетерминированной машине Тьюринга]] за время ''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}}

NTIME - История изменений

WikiSysop: 1 версия