Более формально:
Язык принадлежит классу ,
если существует недетерминированная машина ТьюрингаT, разрешающая данный язык, и сложность ее работы в наихудшем случае, , т.е. не превышает t(n), где n-длина входного слова.
Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
