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