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-Schwierigkeit 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.

Beispiele für EXPTIME-vollständige Probleme[Bearbeiten | Quelltext bearbeiten]

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) [2]
  • Dame [3]
  • Go mit den japanischen Ko-Regeln [4]

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. [5] [6]

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)
  2. 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.
  3. J. M. Robson, N by N checkers is Exptime complete, SIAM Journal on Computing, Band 13, 1984, S. 252–267
  4. J. M. Robson, The complexity of Go, Information Processing; Proceedings of IFIP Congress. 1983, S. 413–417.
  5. Christos H. Papadimitriou: A Glimpse Beyond. In:Computational Complexity 1995, S. 491–508.
  6. José L. Balcázar, Antoni Lozano, Jacobo Torán: The complexity of algorithmic problems on succinct instances.. In: Computer Science. 1992. doi:10.1007/978-1-4615-3422-8_30.

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • EXPTIME. In: Complexity Zoo. (englisch)