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