Diskussion:EXPTIME
Letzter Kommentar: vor 6 Jahren von Wdvorak in Abschnitt Exptime vollständige Sprache
Beispiele[Quelltext bearbeiten]
Vielleicht sollte mal ein Beispiel angegeben werden für ein Problem, dass in Exp aber nicht in P ist außer dem angegebenen Halteproblem.--Claude J (Diskussion) 09:32, 27. Aug. 2017 (CEST)
- Ist inzwischen erledigt.--Claude J (Diskussion) 22:00, 17. Apr. 2018 (CEST)
Exptime vollständige Sprache[Quelltext bearbeiten]
Ich verstehe das Beispiel nicht. Die Sprache besteht aus dem Output einer deterministischen Turingmaschine bei Input x, die nach höchstens k Schritten hält. Welches Problem soll da exptime vollständig sein ? Nach englischer Wiki die Variante des Halteproblems in k Schritten.--Claude J (Diskussion) 21:53, 17. Apr. 2018 (CEST)
- Erstens Danke für die Umfomulierung im Artikel - jetzt ist es klarer.
- Die Sprache besteht aus Tripeln die (a) eine Codierung/Beschreibung einer deterministischen Turingmaschine M enthalten, (b) eine Eingabe x für diese Maschine und (c) eine positive ganze Zahl k (in Binärcodierung), und zu sätzlich erfüllen dass die Maschine M mit Eingabe x nach maximal k Schritten terminiert.
- Das EXPTIME vollständige Problem ist jetzt wenn man ein Tripel (M,x,k) gegeben hat zu entscheiden ob tatsächlich die Bedingung dass M mit Eingabe x nach maximal k Schritten terminiert hält, d.h. ob ein Tripel in der Sprache ist oder nocht.
- Das Problem wird auch als Wortproblem der Sprache bezeichnet und ist das kanonische Problem zu formalen Sprachen in der theoretischen Informatik.
- - Wdvorak (Diskussion) 09:30, 18. Apr. 2018 (CEST)