From Wikipedia, the free encyclopedia

In computational complexity theory, NLIN is the class of decision problems that can be solved by a nondeterministic multitape Turing machine in linear time, O(n). It is known that this class differs from its deterministic counterpart, DLIN. [1]

References

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

In computational complexity theory, NLIN is the class of decision problems that can be solved by a nondeterministic multitape Turing machine in linear time, O(n). It is known that this class differs from its deterministic counterpart, DLIN. [1]

References

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

Videos

Youtube | Vimeo | Bing

Websites

Google | Yahoo | Bing

Encyclopedia

Google | Yahoo | Bing

Facebook