Jump to content

英文维基 | 中文维基 | 日文维基 | 草榴社区

DLIN

From Wikipedia, the free encyclopedia

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

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