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{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)$

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

$\mbox{NEXP} = \bigcup_{k\in\mathbb{N}} \mbox{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

$\mbox{NTIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))$.

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

$\mbox{NTIME}(t(n)) \subseteq \mbox{ATIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))$.

References

Complexity Zoo: NTIME(f(n)).

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Theoretical computer science stubs Computational resources Complexity classes Wikimedia Foundation. 2010. Игры ⚽ Поможем написать курсовую DTIME Focal (HP-41) Look at other dictionaries: NTIME — En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de… …   Wikipedia Español NTIME — En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado. La clase de… …   Enciclopedia Universal NTIME — In der Komplexitätstheorie steht für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können. Mittels Diagonalisierung lässt sich zeigen, dass die Hierarchie echt ist. Kategorie:… …   Deutsch Wikipedia ntime — centime intime …   Dictionnaire des rimes ntimé — intimé …   Dictionnaire des rimes Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia Turingmaschine mit Zusatzeingabe — Eine Turingmaschine mit Zusatzeingabe ist ein zu Nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der Theoretischen Informatik. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Definition 2.1 Turingmaschine mit Zusatzeingabe …   Deutsch Wikipedia 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 …   Wikipedia Teorema de la jerarquía temporal — En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”