|
|
| (не показана 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}}
| + | |
