NTIME
From Wikipedia, the free encyclopedia
(Redirected from Nondeterministic time)
In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(f(n)), and unlimited space.
The well-known complexity class NP can be defined in terms of NTIME as follows:
Similarly, the class NEXPTIME is defined in terms of NTIME. The non-deterministic time hierarchy theorem says that nondeterministic machines can solve more problems in asymptotically more time.
 |
This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |
