NTIME

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 complejidad NP se puede definir en términos de NTIME como:

\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)

Wikimedia foundation. 2010.

См. также в других словарях:

  • 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… …   Wikipedia

  • 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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»