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

12

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

Marzio De Biasi
quelle
1
Fast jedes PSPACE-vollständige Problem hat viele Sonderfälle, die niemand studiert hat. Wie definieren Sie ein offenes Problem ?
RB
@RB: "offenes Problem" Ein Problem, das derzeit untersucht wird (oder untersucht wurde, einige Male zitiert wurde, ...), und Forscher halten es für interessant, es zu lösen (zumindest, um die Grenze von PSPACE-vollständigen Problemen zu formen) ... im Schatten des P vs PSPACE-Daemons :-).
Marzio De Biasi
1
TAUT ist eine eingeschränkte Version von QBF, und es ist ein offenes Problem, ob es PSPACE- oder NP-schwer ist, so dass es alle Anforderungen erfüllt, aber irgendwie glaube ich nicht, dass es im richtigen Sinne ist.
Emil Jeřábek unterstützt Monica am
@ EmilJeřábek: QBF beschränkt auf eine endliche Anzahl von Quantifizierern könnte im Geiste liegen (dh PH vs PSPACE) ... aber es ist ein Sprung von "unendlich nach endlich"; Ich interessiere mich mehr für Beschränkungen der endlichen "Strukturen" des Problems.
Marzio De Biasi

Antworten:

11

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.PSPACENP

http://arxiv.org/abs/1409.1530

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

Tom van der Zanden
quelle
11

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 .

Ryan Williams
quelle
(Nicht im Zusammenhang mit dieser Antwort, aber trotzdem.) Woher wissen wir, dass das Problem der 7-dominierenden Menge auf n Knotengraphen in n 7 + o ( 1 ) Zeit gelöst werden kann ? Referenz 17 macht nur diese Behauptung für l ≥ 8. 7+o(1)
(Ich hätte das früher erwähnen sollen, aber) Ich habe jetzt eine Frage zum Fall k = 7 auf dieser Site.
4

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).rrL(r)L(r)rΣ

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)

r1rnrie=(w1++wm)wjee+e?ea(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.

Thomas S
quelle
2

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


quelle
Haben Sie einen einfachen Beweis oder eine Referenz für die Härte der gegenüberstehenden Version (wobei jeder Knopf eine Tür öffnet und eine andere schließt und jede Tür von einem Knopf geöffnet und von einem anderen geschlossen wird)?
Jonas Kölker
Nein, obwohl ich weiß, wie man Härte zeigt, selbst wenn alle Türen geschlossen sind, was ich wahrscheinlich in diesem Jahr veröffentlichen werde.
Ich glaube, ich habe auch eine Idee, wie das geht. Würdest du mir eine Kopie deines Manuskripts schicken, wenn es angenommen wird? Ich würde gerne Ideen vergleichen :-) [bezüglich: die Härte gegen Vorzeichen, IINM die Reduzierung des Bloxorz-Papiers ist sowohl an Türen als auch an Knöpfen gegen Vorzeichen.]
Jonas Kölker
Ja.