Diskussion:EXPTIME

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 6 Jahren von Wdvorak in Abschnitt Exptime vollständige Sprache
Zur Navigation springen Zur Suche springen

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)Beantworten

Ist inzwischen erledigt.--Claude J (Diskussion) 22:00, 17. Apr. 2018 (CEST)Beantworten

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)Beantworten

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)Beantworten