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).

Meaning

This means that there is a non-deterministic machine which, for a given input of size n, will run in time O(f(n)) (i.e. within a constant multiple of f(n), for n greater than some value), and will always "reject" the input if the answer to the decision problem is "no" for that input, while if the answer is "yes" the machine will "accept" that input for at least one computation path. Equivalently, there is a deterministic Turing machine M that runs in time O(f(n)) and is able to check a polynomial-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.

Space constraints

The space available to the machine is not limited, although it cannot exceed O(f(n)), because the time available limits how much of the tape is reachable.

Relation to other complexity classes

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

{\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})

Similarly, the class NEXP is defined in terms of NTIME:

{\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})

The non-deterministic time hierarchy theorem says that nondeterministic machines can solve more problems in asymptotically more time.

NTIME is also related to DSPACE in the following way. For any time constructible function t(n), we have

{\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))

A generalization of NTIME is ATIME, defined with alternating Turing machines. It turns out that

{\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))

References

Complexity Zoo: NTIME(f(n)).

Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.