EXPTIME

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Zusammenhang mit anderen Komplexitätsklassen

In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch beschränkter Zeit entschieden werden können. ist dabei ein beliebiges Polynom in der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also:

EXPTIME-Vollständigkeit[Bearbeiten | Quelltext bearbeiten]

Die Sprache ist ein Beispiel für eine EXPTIME-vollständige Sprache.[1] Der Grund für die EXPTIME-Härte liegt intuitiv darin, dass die Zahl exponentiell größer als die Länge ihrer Kodierung im Wort ist, und es zum Entscheiden, ob auf nach höchstens Schritten hält, im Allgemeinen keine effizientere Möglichkeit gibt, als auf für Schritte zu simulieren.

Beziehung zu anderen Komplexitätsklassen[Bearbeiten | Quelltext bearbeiten]

Die folgenden Beziehungen sind bekannt:

NC P NP PSPACE EXPTIME NEXPTIME

Da P nach dem Zeithierarchiesatz eine echte Teilmenge von EXPTIME ist, muss mindestens eine Teilmengenbeziehungen P NP PSPACE EXPTIME echt sein. Es wird vermutet, dass alle Inklusionen echt sind.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Chris Umans: CS21: Decidability and Tractability, Lecture 18 (PDF; 133 kB)

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • EXPTIME. In: Complexity Zoo. (englisch)