Ntzeit

Im Computerkomplexitätstheorie, das Komplexitätsklasse Time (f(n)) ist der Satz von Entscheidungsprobleme das kann durch a gelöst werden Nichtdeterministische Turing-Maschine das läuft rechtzeitig O(f(n)). Hier O ist der Big O Notation, f ist eine Funktion und n ist die Größe der Eingabe (für die das Problem entschieden werden soll).

Bedeutung

Dies bedeutet, dass es eine nicht deterministische Maschine gibt, die für einen gegebenen Eingang der Größe n, wird rechtzeitig laufen O(f(n)) (d. H. Innerhalb eines konstanten Mehrfaches von f(n), zum n größer als ein Wert) und wird die Eingabe immer "ablehnen", wenn die Antwort auf das Entscheidungsproblem für diese Eingabe "Nein" lautet, während die Antwort "Ja" ist, "akzeptiert" diese Eingabe für mindestens eine Berechnung Weg. Äquivalent gibt es a deterministische Turing -Maschine M Das läuft rechtzeitig O(f(n)) und ist in der Lage, eine zu überprüfen O(f(n))-Längenzertifikat für eine Eingabe; Wenn die Eingabe eine "Ja" -Instanz ist, wird mindestens ein Zertifikat akzeptiert. Wenn die Eingabe eine "Nein" -Instanz ist, kann kein Zertifikat den Maschine akzeptieren lassen.

Raumbeschränkungen

Der für die Maschine zur Verfügung stehende Speicherplatz ist nicht begrenzt, obwohl er nicht überschreiten kann O(f(n)), weil die verfügbare Zeit begrenzt, wie viel Klebeband erreichbar ist.

Beziehung zu anderen Komplexitätsklassen

Die bekannte Komplexitätsklasse Np kann in Bezug auf die Zeit wie folgt definiert werden:

Ebenso die Klasse Nexp ist in Bezug auf die Zeit definiert:

Die nicht deterministischen Zeithierarchie Theorem Sagt, dass nichtdeterministische Maschinen mehr Probleme in asymptotisch mehr Zeit lösen können.

NTION ist auch mit dem Zusammenhang mit DSpace auf die folgende Weise. Für jeden Zeitkonstruktibel Funktion t(n), wir haben

.

Eine Verallgemeinerung von Ntzeit ist EINE ZEIT, definiert mit Wechsel Turing -Maschinen. Es stellt sich heraus, dass

.

Verweise

Komplexitätszoo: Time (f(n)).