EXPTIME
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 <math>\mathcal O\left(2^{p(n)}\right)</math> beschränkter Zeit entschieden werden können. <math>p\left(n\right)</math> ist dabei ein beliebiges Polynom in der Eingabelänge <math>n</math>. In der DTIME-Notation ausgedrückt gilt also:
- <math>\mbox{EXPTIME} = \bigcup_{k \in \mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right).</math>
EXPTIME-Vollständigkeit
Ein Problem ist EXPTIME-vollständig, wenn es in EXPTIME ist und jedes Problem in EXPTIME in Polynomialzeit auf dieses zurückgeführt werden kann (Polynomialzeitreduktion). Während die Frage der Gleichheit von P und NP ein berühmtes offenes Problem der Informatik ist (P-NP-Problem, speziell ob NP-vollständige Probleme in P liegen), ist bei EXPTIME-vollständigen Problemen bekannt, dass sie nicht in P liegen. Das folgt auch aus dem Zeithierarchiesatz.
Ein Beispiel ist eine Variante des Halteproblems für deterministische Turingmaschinen, zu entscheiden ob diese bei gegebenem Input in höchstens k Schritten hält. Die Sprache <math>\mathcal{L} = \{ \langle M, x, k \rangle \mid M \mbox{ ist eine DTM, die bei Eingabe } x \mathrm{\ nach\ h\ddot ochstens\ } k \mathrm{\ Schritten\ h\ddot alt}\}</math> ist ein Beispiel für eine EXPTIME-vollständige Sprache und das erwähnte Halteproblem entspricht dem Wortproblem in dieser Sprache.<ref name="CS21" /> Der Grund für die EXPTIME-Schwierigkeit liegt intuitiv darin, dass die Zahl <math>k</math> exponentiell größer ist als die Länge ihrer Kodierung (<math>\log k</math> bits), und es zum Entscheiden, ob <math>M</math> auf <math>x</math> nach höchstens <math>k</math> Schritten hält, im Allgemeinen keine effizientere Möglichkeit gibt, als <math>M</math> auf <math>x</math> für <math>k</math> Schritte zu simulieren.
Beispiele für EXPTIME-vollständige Probleme
Mehrere Beispiele für EXPTIME-vollständige Probleme sind Zweipersonenspiele. Die konkrete Fragestellung ist, ob ein Spieler aus einer gegebenen Spielposition eine Strategie hat, um das Spiel sicher zu gewinnen. Beispiele für EXPTIME-vollständige Spiele sind
- verallgemeinertes Schach (auf einem n x n Brett für beliebig hohe n, die erforderliche Zeit wächst exponentiell mit n)<ref>Aviezri Fraenkel, D. Lichtenstein, Computing a perfect strategy for n×n chess requires time exponential in n, J. Comb. Th. A, Band 31, 1981, S. 199–214.</ref>
- Dame<ref>J. M. Robson, N by N checkers is Exptime complete, SIAM Journal on Computing, Band 13, 1984, S. 252–267</ref>
- Go mit den japanischen Ko-Regeln<ref>J. M. Robson, The complexity of Go, Information Processing; Proceedings of IFIP Congress. 1983, S. 413–417.</ref>
Alle diese Spiele haben die Eigenschaft gemeinsam, dass ein Spiel exponentiell viele Züge haben kann. Spiele, die nur polynomiell viele Züge pro Spiel erlauben und bei denen eine Spielposition polynomiell beschrieben werden, können in PSPACE gelöst werden.
Eine andere Quelle für EXPTIME-vollständige sind Graph-Probleme, bei denen die Eingabe durch einen kompakten Schaltkreis repräsentiert wird. Dieser Schaltkreis kann exponentiell kleiner sein als eine explizite Repräsentation des Graphen. Da die Komplexität im Verhältnis zur Eingabegröße angegeben wird, sind viele Probleme, die mit einer expliziten Repräsentation P-vollständig sind, bei der Schaltkreis-Repräsentation EXPTIME-vollständig.<ref>{{#invoke:Vorlage:Literatur|f}}{{#if: | {{#if: Vorlage:Cite book/ParamBool | Vorlage:Toter Link/archivebot | Vorlage:Webarchiv/archiv-bot }}
}}{{#invoke:TemplatePar|check
|all = title= |opt = vauthors= author= author-link= authorlink= author1= author-link1= author1-link= first= last= first1= last1= first2= last2= author2= first3= last3= author3= first4= last4= author4= first5= last5= author5= first6= last6= author6= first7= last7= author7= first8= last8= author8= others= coauthors= script-title= trans-title= orig-date= orig-year= chapter= chapter-url= editor= editor-first= editor-last= editor-first1= editor-last1= editor-first2= editor-last2= editor-first3= editor-last3= editor-link= editor-link1= language= format= others= series= issue= number= edition= volume= publisher= location= date= year= isbn= page= at= pages= arxiv= doi= jstor= bibcode= pmc= pmid= lccn= oclc= id= url= url-status= access-date= accessdate= archive-url= archiveurl= archive-date= archivedate= quote= url-access= ref= coauthors= origyear= archivebot= offline= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite book |errNS = 0 |template = Vorlage:Cite book |format = |preview = 1
}}Vorlage:Cite book/URLVorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool | Vorlage:Cite book/Meldung }}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:Christos H. Papadimitriou|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:491–508|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref>
<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:
| {{#if: Vorlage:Cite book/ParamBool
| Vorlage:Toter Link/archivebot
| Vorlage:Webarchiv/archiv-bot
}}
}}{{#invoke:TemplatePar|check
|all = title=
|opt = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical= name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx= accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
|errNS = 0
|template = Vorlage:Cite journal
|format =
|preview = 1
}}Vorlage:Cite book/URL{{#if: | Vorlage:Cite book/Meldung }}{{#if: | Vorlage:Cite book/Meldung }}{{#if: Computer Science
|| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}{{#if: Vorlage:Cite book/ParamBool
| Vorlage:Cite book/Meldung
}}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:José L. Balcázar, Antoni Lozano, Jacobo Torán|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
| Vorlage:Cite book/Meldung
}}</ref>
Beziehung zu anderen Komplexitätsklassen
Die folgenden Beziehungen sind bekannt:
- NC <math>\subseteq</math> P <math>\subseteq</math> NP <math>\subseteq</math> PSPACE <math>\subseteq</math> EXPTIME <math>\subseteq</math> NEXPTIME
Da P nach dem Zeithierarchiesatz eine echte Teilmenge von EXPTIME ist, muss mindestens eine der Teilmengenbeziehungen P <math>\subseteq</math> NP <math>\subseteq</math> PSPACE <math>\subseteq</math> EXPTIME echt sein. Es wird vermutet, dass alle Inklusionen echt sind.
Einzelnachweise
<references> <ref name="CS21">Chris Umans: CS21: Decidability and Tractability, Lecture 18 (PDF; 133 kB)</ref> </references>
Weblinks
- EXPTIME. In: Complexity Zoo. (englisch)