НЛИН
В сложности вычислений теории NLIN — это класс задач решения, которые могут быть решены с помощью недетерминированной многоленточной машины Тьюринга за линейное время O ( n ). Известно, что этот класс отличается от своего детерминированного аналога DLIN . [1]
Ссылки
[ редактировать ]- ^ Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1990). Структурная сложность II . Спрингер Верлаг. ISBN 3-540-52079-1 . , Теорема 3.9