Misplaced Pages

NLIN

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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.

References

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

This theoretical computer science–related article is a stub. You can help Misplaced Pages by expanding it.

Categories:
NLIN Add topic