NTIME

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 which runs in time O(f(n)).

Here O is the big O notation, f is some function, and n is the size of the input (for which the problem is to be decided).

Equivalently, there is a deterministic Turing machine M that runs in time O(f(n)) and is able to check an O(f(n))-length certificate for an input; if the input is a "yes" instance, then at least one certificate is accepted, if the input is a "no" instance, no certificate can make the machine accept.

The well-known complexity class NP can be defined in terms of NTIME as follows: Similarly, the class NEXP is defined in terms of NTIME: The non-deterministic time hierarchy theorem says that nondeterministic machines can solve more problems in asymptotically more time.

For any time constructible function t(n), we have A generalization of NTIME is ATIME, defined with alternating Turing machines.