EXPSPACE-vollständige Probleme

Ich versuche derzeit, EXPSPACE-vollständige Probleme zu finden (hauptsächlich, um Inspiration für eine Reduzierung zu finden), und ich bin überrascht über die geringe Anzahl an Ergebnissen, die sich ergeben.

Bisher habe ich diese gefunden, und ich habe Probleme, die Liste zu erweitern:

• Universalität (oder andere Eigenschaften) von regulären Ausdrücken mit Potenzierung.
• Probleme im Zusammenhang mit Vektoradditionssystemen
• Nicht beobachtbare Spiele (siehe zum Beispiel diesen Blog )
• ein Fragment von FO-LTL, in Über die rechnerische Komplexität entscheidbarer Fragmente linearer zeitlicher Logik erster Ordnung

Kennen Sie andere Kontexte, in denen EXPSPACE-Vollständigkeit auf natürliche Weise auftritt?

Die Erweiterung des Beispiels von Emil Jerabek in den Kommentaren darauf hingewiesen, entstehen -komplette Probleme natürlich alle über algebraische Geometrie. Dies begann (glaube ich) mit dem Ideal Membership Problem ( Mayr-Meyer und Mayr ) und damit der Berechnung der Gröbner-Basen. Dies wurde dann auf die Berechnung von Syzygien ( Bayer und Stillman ) ausgeweitet . Viele natürliche Probleme in der rechnerischen algebraischen Geometrie sind mit einem dieser Probleme gleichzusetzen. Siehe auch die Bayer-Mumford-Umfrage "Was kann in algebraischer Geometrie berechnet werden?"$\mathsf{EXPSPACE}$

Viele Probleme, die PSPACE-vollständig sind, werden EXPSPACE-vollständig, wenn die Eingabe "genau" angegeben wird, dh über eine Codierung, mit der Sie Eingaben beschreiben können, die normalerweise exponentiell groß sind.

Hier ein Beispiel für endliche Automaten (entsprechend für gerichtete Graphen mit beschrifteten Kanten): Die Entscheidung, ob zwei Automaten dieselbe Sprache akzeptieren (denselben Satz beschrifteter Pfade von einem Ursprungsknoten zu einem Zielknoten haben), ist PSPACE-vollständig. Wenn die Automaten (Graphen) durch Boolesche Formeln gegeben sind (Knoten sind Bewertungen v, v ', .. und es gibt Boolesche Formeln, die angeben, ob va-> v' eine Kante ist), wird das Problem EXPSPACE-vollständig. NB: Es gibt viele andere Möglichkeiten, einen großen Graphen / Automaten genau zu definieren, siehe z . B. dieses Dokument .

Das Beispiel mit regulären Ausdrücken passt zu diesem Muster. Wenn Sie eine ".. ^ 2" -Notation für das Quadrieren einführen, können Sie kompakte reguläre Ausdrücke schreiben, die sehr groß wären, wenn Sie jedes "(foo) ^ 2" durch "foo foo" und "((Balken) ^ 2) erweitern würden. ^ 2 "von" bar bar bar bar ". Natürlich werden einige Probleme, die ohne Quadrieren PSPACE-vollständig sind, zu EXPSPACE-vollständig, wobei Quadrieren zulässig ist. Hier ist die klassische Referenz . [NB: Andere Beispiele wie reguläre Ausdrücke mit Schnittmenge oder mit Ergänzungen passen offensichtlich nicht zum Muster der neuen Notation, die in der Standardnotation zu einer exponentiell größeren Eingabe erweitert wird.]

Ebenso kann ein LOGSPACE-vollständiges Problem (z. B. die Erreichbarkeit in gerichteten Diagrammen) EXPSPACE-vollständig werden, wenn Ihre prägnante Codierung die Beschreibung von Diagrammen mit doppelt exponentieller Größe ermöglicht.

Fazit: Sie können leicht neue, wenn auch künstliche, EXPSPACE-vollständige Probleme finden, indem Sie die klassischen PSPACE- oder LOGSPACE-Probleme (von denen Sie viele finden werden) berücksichtigen und eine kompakte / prägnante / ... Codierung der Eingabe ermöglichen.

Die zeitliche Planung mit gleichzeitigen Aktionen ist EXPSPACE-vollständig, wie in gezeigt

J. Rintanen, „Komplexität der gleichzeitigen zeitlichen Planung“, Tagungsband der 17. Internationalen Konferenz für automatisierte Planung und Planung, S. 280–287, 2007

$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• $d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$

$d$

Die meisten Standardklassen ab PSPACE (auch für NP, wenn Sie möchten) haben einige Kachelprobleme als vollständiges Problem. Solche Kachelprobleme sind nicht so weit von den auf natürlichen Turingmaschinen basierenden vollständigen Problemen entfernt, aber sie sind häufig als Ausgangspunkt für Reduktionen recht praktisch. Zusammenfassend lässt sich sagen, dass ein Kachelproblem eine Reihe zulässiger Kacheln (d. H. Kacheltypen, aus denen Sie beliebig viele Kacheln verwenden können) enthält und regelt, wie sie kombiniert werden können, häufig durch eine Reihe H horizontal zulässiger Paare von Kacheln Kacheln und eine Menge V von vertikal erlaubten Typen. Darüber hinaus kann ein erstes und ein letztes Feld angegeben werden und abhängig von der aktuellen Version und der Anzahl der Zeilen und / oder Spalten, die das Feld enthalten soll. Die algorithmische Frage ist, ob es eine korrekte Kachelung gibt, dh eine Zuordnung von Positionen zu Kacheln. das befolgt alle Beschränkungen und hat das Startfeld in der unteren linken Position und das letzte Feld in der oberen rechten Position. (Es gibt viele Variationen bezüglich der genauen Definitionen).

Für die vorliegende Klasse, EXPSPACE, können Sie zwischen (mindestens) zwei Versionen wählen:

• Exponentialbreiten-Korridor-Tiling, bei dem ein Parameter n angegeben ist und die Frage lautet, ob es ein Tiling mit 2 ^ n Spalten und einer beliebigen Anzahl von Zeilen gibt
• exp-times-exp Tiling-Spiel, bei dem das Tiling mit n die Größe 2 ^ n mal 2 ^ n haben soll, wobei der erste Spieler ein korrektes Tiling erreichen will und der zweite Spieler dies zu verhindern versucht.

Papiere zum Anschauen sind - Bogdan S. Chlebus: "Domino-Tiling Games". J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: "Die Bequemlichkeit von Fliesen", in: Komplexität, Logik und Rekursionstheorie, Lecture Notes in Pure and Applied Mathematics, Vol. 187, 1997, S. 331–363.

Ein Beispiel und ein Beweis dafür, dass jeder nicht deterministische Algorithmus für die Theorie der Reelle erster Ordnung mit Addition NExpTime-hard ist, finden Sie in Einführung in die Automatentheorie, Sprachen und Berechnung von Hopcroft / Ullman Thm13.16. daher ist es vermutlich auch NExpSpace-schwer, es sei denn, ein theoretischer Durchbruch beweist, dass es "auf engem Raum" gelöst werden kann, aber diese Frage ist natürlich ähnlich (fast identisch?) zu L =? P. (Mit anderen Worten, alle bekannten NExpTime-hard-Probleme sind auch grundlegende Kandidaten für NExpSpace-hard, und wenn dies nachweislich nicht der Fall ist, würde dies wahrscheinlich einen Durchbruch bei der Lösung einer langoffenen Komplexitätsklassentrennung bedeuten.) Der Beweis stammt von Fischer, Rabin 1974, "Super-exponentielle Komplexität der Presburger-Arithmetik", Complexity of Computation(R. Karp ed.). Proceedings of SIAM-AMS Symposium in Angewandter Mathematik.