NLIN
In computational complexity theory, NLIN is the class of decision problems that can be solved by a nondeterministic multitape Turing machine in linear time. It is known that this class differs from its deterministic counterpart, DLIN.[1]
References
[edit]- ↑ Balcázar, Díaz & Gabarró (1990), theorem 3.9.
- Balcázar, Jose Luis; Díaz, Josep; Gabarró, Joaquim (1990). Structural Complexity II. Monographs in Theoretical Computer Science. Vol. 22. Berlin, Heidelberg: Springer. ISBN 3-540-52079-1.
