NSPACE

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

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

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

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