„EXPTIME“ – Versionsunterschied

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

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).}$

Die Sprache Fehler beim Parsen (Syntaxfehler): {\displaystyle \{ \langle M, x, k \rangle \mid \mbox{ $M$ ist eine DTM, die bei Eingabe $x$ nach höchstens $k$ Schritten hält}\}} ist EXPTIME-vollständig.^[1]

Die folgenden Beziehungen sind bekannt:

NC ${\displaystyle \subseteq }$ P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME

Da P nach dem Zeithierarchiesatz eine echte Teilmenge von EXPTIME ist, muss mindestens eine Teilmengenbeziehungen P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME echt sein.

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

• EXPTIME. In: Complexity Zoo. (englisch)