NSPACE

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Класс NSPACE(s(n)) означает класс задач, разрешимых на недетерминированной машине Тьюринга, использующей не более s(n) ячеек.

Более формально:

Язык \(L \subset \Sigma^*\) принадлежит классу \({\cal NSPACE}(s(n))\), если существует недетерминированная машина Тьюринга T, разрешающая данный язык, и число используемых ею ячеек ленты на входе длины n не превышает s(n).


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.