Definitions

# 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 using time O(f(n)), and unlimited space.

The well-known complexity class NP can be defined in terms of NTIME as follows:

$mbox\left\{NP\right\} = bigcup_\left\{kinmathbb\left\{N\right\}\right\} mbox\left\{NTIME\right\}\left(n^k\right)$

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.

Search another word or see unlimited spaceon Dictionary | Thesaurus |Spanish