„EXPTIME“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][gesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
→‎EXPTIME-Vollständigkeit: weiteres beispiel, siehe auch engl wiki
→‎EXPTIME-Vollständigkeit: Beispiele für vollständige Probleme
Zeile 7: Zeile 7:
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.<ref name="CS21" /> Der Grund für die EXPTIME-Schwierigkeit liegt intuitiv darin, dass die Zahl <math>k</math> exponentiell größer als die Länge ihrer Kodierung im Wort <math>\langle M, x, k \rangle</math> ist, 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.
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.<ref name="CS21" /> Der Grund für die EXPTIME-Schwierigkeit liegt intuitiv darin, dass die Zahl <math>k</math> exponentiell größer als die Länge ihrer Kodierung im Wort <math>\langle M, x, k \rangle</math> ist, 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 ===
Weitere Beispiele für EXPTIME-vollständige Probleme außer dem Halteproblem sind die strategische Auswertung der Spielpositionen bei verschiedener Zweipersonenspiele wie verallgemeinertes Schach (auf einem n x n Brett für beliebig hohe n, die erforderliche Zeit wächst exponentiell mit n), Dame und Go mit den japanischen Ko-Regeln.<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><ref>J. M. Robson, N by N checkers is Exptime complete, SIAM Journal on Computing, Band 13, 1984, S. 252–267</ref><ref>J. M. Robson, The complexity of Go, Information Processing; Proceedings of IFIP Congress. 1983, S. 413–417.</ref>
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 das 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 [[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 eine explizite Repräsentation des Graphen.
Da die Komplexität im Verhältnis zur Eingabegröße angegeben wird sind viele Probleme die mit
einer explizite Repräsentation [[P]]-vollständig sind bei der Schaltkreis-Repräsentation EXPTIME-vollständig.
<ref>{{Cite book| author = Christos H. Papadimitriou | chapter = A Glimpse Beyond| title = Computational Complexity |year = 1995| pages = 491–508}}</ref>
<ref>{{cite journal| author = José L. Balcázar, Antoni Lozano, Jacobo Torán| title = The complexity of algorithmic problems on succinct instances. | journal =Computer Science| year = 1992| doi = 10.1007/978-1-4615-3422-8_30}}</ref>


== Beziehung zu anderen Komplexitätsklassen ==
== Beziehung zu anderen Komplexitätsklassen ==

Version vom 28. August 2017, 20:42 Uhr

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

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

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 das 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 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 eine explizite Repräsentation des Graphen. Da die Komplexität im Verhältnis zur Eingabegröße angegeben wird sind viele Probleme die mit einer explizite Repräsentation P-vollständig sind bei der Schaltkreis-Repräsentation EXPTIME-vollständig. [5] [6]

Beziehung zu anderen Komplexitätsklassen

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

  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: Computational Complexity. 1995, A Glimpse Beyond, 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

  • EXPTIME. In: Complexity Zoo. (englisch)
Abgerufen von „https://de.wikipedia.org/w/index.php?title=EXPTIME&oldid=168573297“