computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, the

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

NTIME(''f''(''n'')) is the set of

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...

s that can be solved by a

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

which runs in time ''O''(''f''(''n'')). Here ''O'' is the

big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...

, ''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 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.

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 = \bigcup_ \mathsf(n^k)

Similarly, the class

NEXP In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^. In terms of NTIME, :\mathsf = \bigcup_ \mathsf(2^) ...

is defined in terms of NTIME: :

\mathsf = \bigcup_ \mathsf(2^)

The non-deterministic

time hierarchy theorem In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, ...

says that nondeterministic machines can solve more problems in asymptotically more time. NTIME is also related to

DSPACE DSpace is an open source repository software package typically used for creating open access repositories for scholarly and/or published digital content. While DSpace shares some feature overlap with content management systems and document manag ...

in the following way. For any time constructible function ''t''(''n''), we have :

\mathsf(t(n)) \subseteq \mathsf(t(n))

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

\mathsf(t(n)) \subseteq \mathsf(t(n)) = \mathsf(t(n))

References

. {{DEFAULTSORT:Ntime Computational resources Complexity classes