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 \mathcal O\left(2^{p(n)}\right) beschränkter Zeit entschieden werden können. p\left(n\right) ist dabei ein beliebiges Polynom in der Eingabelänge n. In der DTIME-Notation ausgedrückt gilt also:

\mbox{EXPTIME} = \bigcup_{k \in \mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right).

EXPTIME-Vollständigkeit[Bearbeiten]

Die Sprache \mathcal{L} = \{ \langle M, x, k \rangle \mid M \mbox{ ist eine DTM, die bei Eingabe } x \mbox{ nach höchstens } k \mbox{ Schritten hält}\} 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 k exponentiell größer als die Länge ihrer Kodierung im Wort \langle M, x, k \rangle ist, und es zum Entscheiden, ob M auf x nach höchstens k Schritten hält, im Allgemeinen keine andere Möglichkeit gibt, als M auf x für k Schritte zu simulieren.

Beziehung zu anderen Komplexitätsklassen[Bearbeiten]

Die folgenden Beziehungen sind bekannt:

NC \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME

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

Einzelnachweise[Bearbeiten]

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

Weblinks[Bearbeiten]

  • EXPTIME. In: Complexity Zoo. (englisch)