NTIME
Sign in to saveIn 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 that runs in time O(f(n)), where 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).
Article · Deutsch
In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können. Mittels NTIME werden unter anderem folgende Komplexitätsklassen definiert bzw. charakterisiert: * Q=NTIME(n) (Formal wird Q als Familie aller Sprachen L mit L=L(M) definiert, wobei jede Berechnung von M auf Eingabe w höchstens |w| Schritte benötigt. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.) * NP:= NTIME(nk) * NE:=NTIME(2O(n)) * NEXP:= NTIME(2nk) Mittels Diagonalisierung lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie Q ⊂ NP ⊂ NE ⊂ NEXP echt sind.
Abstract from DBpedia / Wikipedia · CC BY-SA