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 \{ \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 EXPTIME-vollständig.[1]

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.

Einzelnachweise[Bearbeiten]

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

Weblinks[Bearbeiten]

  • EXPTIME. In: Complexity Zoo. (englisch)