DLIN

In computational complexity theory, DLIN is the class of decision problems that can be solved by a multitape Turing machine in linear time, O(n). It is known that this class differs from its nondeterministic counterpart, NLIN.{{cite book |last1=Balcazar |first1=Jose Luis |last2=Diaz |first2=Josep |last3=Gabarro |first3=Joaquim |title=Structural Complexity II |date=1990 |publisher=Springer Verlag |isbn=3-540-52079-1}}, Theorem 3.9