Более формально:
Язык принадлежит классу ,
если существует недетерминированная машина ТьюрингаT, разрешающая данный язык, и число используемых ею ячеек ленты на входе длины n не превышает s(n).
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
