Article · Wikipedia archive · Last revised May 31, 2026

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.

Last revised
May 31, 2026
Read time
≈ 1 min
Length
54 w
Citations
1
Source
Wikipedia ↗

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.1

References

References

  1. Balcazar, Jose Luis; Diaz, Josep; Gabarro, Joaquim (1990). Structural Complexity II. Springer Verlag. ISBN 3-540-52079-1., Theorem 3.9