Probleme, von denen nicht bekannt ist, dass sie PSPACE-vollständig sind

Was sind Probleme mit den folgenden Eigenschaften:

1) Sie beschränken (möglicherweise bekannte) Probleme, die PSPACE-vollständig sind.

2) Die eingeschränkten Versionen sind in PSPACE, aber es ist ein offenes Problem, wenn sie PSPACE-vollständig sind (oder auch wenn sie NP-hart sind).

Vier Beispiele aus "Puzzles & C.":

• Die Komplexität von 1x1 Rush Hour [1] (PSPACE-vollständig für Blöcke der Größe 2x1);
• [ Gelöst ] Die Komplexität von planarem Subway Shuffle [1] (PSPACE-vollständig, auch für planare Graphen kann ein Entwurf des Papiers hier heruntergeladen werden );
• Die Komplexität von Lunar-Lockout ohne feste Blöcke [1] (PSPACE-komplett mit festen Blöcken);
• (nicht so berühmt) Die Komplexität des (my) Switch-Netzwerk-Problems (es ist eine Einschränkung des PSPACE-vollständigen Sokoban, NP-schwer im nicht-planaren Fall, siehe diese Q & A auf cstheory ).

Wenn Sie viele haben, gruppieren Sie sie nach Themen.

[1] Robert A. Hearn, Erik D. Demaine: Spiele, Rätsel und Berechnungen. AK Peters 2009, ISBN 978-1-56881-322-6, S. I-IX, 1-237

Retrogrades Schach. Es ist -vollständig, wenn Sie beliebig viele Könige haben dürfen und keiner von ihnen jederzeit in Schach sein kann. Wenn keine (oder nur einer pro Spieler) Könige erlaubt sind, ist bekannt, dass es Positionen gibt, die exponentielle Bewegungen erfordern, aber das Problem ist bekanntermaßen nur N P -hart.$PSPACE$$NP$

http://arxiv.org/abs/1409.1530

/mathpro/27944/die-hier-existieren-Schachpositionen-dass-exponentiell-viel-zu-erreichende-Vorgänge

Ich bin mir nicht sicher, ob dies Ihrer Vorstellung von Einschränkung entspricht, aber hier ist es.

Das "Minimum QBF-oracle Circuit Size Problem": Gibt es in Anbetracht der Wahrheitstabelle einer Booleschen Funktion und des Parameters k eine Schaltung mit einer Größe von höchstens k, die die Funktion über die Basis AND, OR, NOT und QBF berechnet? (Ein QBF-Gatter interpretiert seine Eingabezeichenfolge als vollständig quantifizierte Boolesche Formel F, und die Ausgabe ist 1, wenn F wahr ist.)

Das Problem liegt definitiv in PSPACE, das unter ZPP-Reduktionen als vollständig bekannt ist, jedoch nicht für deterministische Polynomzeitreduktionen bekannt ist. Unter Logspace-Reduzierungen nachweislich nicht PSPACE-komplett! Siehe Allender, Holden und Kabanets .

Das folgende Problem entspricht in zweifacher Hinsicht der Anforderung ...

Enthalten von regulären Ausdrücken , dh Testen, ob die Sprache eines regulären Ausdrucks in der Sprache eines regulären Ausdrucks r 'enthalten ist (dh ob L ( r ) ⊆ L ( r ' ) ), ist ein wohlbekannter PSPACE- vollständiges Problem, auch wenn r so gewählt Σ * (dann heißt es Universality regulärer Ausdrücke).$r$$r'$$L(r)\subseteq L(r')$$r$$\Sigma^*$

In ähnlicher Weise fragt die Äquivalenz von regulären Ausdrücken , ob und PSPACE-vollständig ist (Härte folgt aus der Universalität ).$L(r)=L(r')$

$r_1\cdots r_n$$r_i$$e=(w_1+\ldots+w_m)$$w_j$$e^*$$e^+$$e?$$e$$a(b+cd)(ab+cde+f)^*d?$

Die Eindämmung von regulären Kettenausdrücken ist immer noch PSPACE-vollständig, aber die Äquivalenz von regulären Kettenausdrücken ist unklar (obwohl bekannt ist, dass sie coNP-hart sind und in PSPACE vorkommen).

Übrigens folgt die PSPACE-Obergrenze leicht, indem die Ausdrücke in NFAs übersetzt und nicht deterministisch nach einem Gegenbeispiel gesucht werden: Errate eine Zeichenfolge Buchstabe für Buchstabe und verfolge die in den NFAs erreichbaren Statusmengen.

Spiele mit nur 2 Knöpfen und 2 Türen, bei denen alle Türen zunächst geschlossen sind:

"Ebenen" sind endliche Untergraphen des planaren Gitters .$\:$ Scheitelpunkte werden als einer von [Start, Schaltfläche, Leer, Tür, Ende] identifiziert. $\:$ Jeder Türscheitelpunkt hat einen Satz Öffnungsknöpfe und einen Satz Schließknöpfe. $\:$ Eine k-Tür ist eine Tür, die von höchstens k Tasten gesteuert wird, und eine k-Taste ist eine Taste, die höchstens k Türen steuert. $\:$ Wann immer sich ein Knopf auf einem Scheitelpunkt befindet, kann man den Knopf drücken, wodurch die Türen geöffnet werden, für die der Knopf ein Öffnungsknopf ist, und die Türen geschlossen werden, für die der Knopf ein Schließknopf ist. $\:$Das Ziel ist es, vom Startknoten zum Endknoten zu gelangen, ohne geschlossene Türen zu betreten.


Solche Ebenen können eindeutig in FPSPACE gelöst werden, und ihre Lösung ist FNPSPACE-schwierig,
selbst wenn [jede Tür genau einen Öffnungsknopf und genau einen Schließknopf hat]
und [jeder Knopf genau eine Tür öffnet und genau eine Tür schließt].
Andererseits heißt es in diesem Artikel : "Es ist ein offenes Problem, ob ein Spiel mit
2 Knöpfen und 2 Türen PSPACE-hart bleibt, wenn alle Türen anfänglich geschlossen sind."


Die FNPSPACE-Härte, wenn alle Türen anfänglich geschlossen sind, wird wiederhergestellt, wenn die Bedingungen aus meinem vorherigen Absatz auf eine der folgenden Arten geändert werden:

Lassen Sie zu, dass Türen 2 Öffnungsknöpfe (zusätzlich zu 1 Schließknopf) haben,
oder
lassen Sie zu, dass Knöpfe 2 Türen schließen (zusätzlich zu 1 Tür).

.


Seite 10 dieses Papiers zeigt, dass die Bestimmung der Lösbarkeit auch ohne Knöpfe und ohne Türen NC1- hart ist .
$\:$Ansonsten kenne ich keine Härteergebnisse für das Lösen von Ebenen mit 2 Knöpfen
und 2 Türen, wenn alle Türen anfänglich geschlossen sind (auch ohne die genau eine von jeder Bedingung).