Problems not known to be PSPACE-complete

Question

What are problems with the following properties:

1) they are restriction of (possibly well known) problems that are PSPACE-complete;

2) the restricted versions are in PSPACE, but it is an open problem if they are PSPACE-complete (or even if they are NP-hard).

Four examples from "puzzles & C.":

• The complexity of 1x1 Rush Hour [1] (PSPACE-complete for blocks of size 2x1 );
• [SOLVED] The complexity of planar Subway Shuffle [1] (PSPACE-complete even for planar graphs, a draft of the paper can be downloaded here );
• The complexity of Lunar-Lockout without fixed blocks [1] (PSPACE-complete with fixed blocks);
• (not so famous) The complexity of (my) Switch-network problem (it is a restriction of the PSPACE-complete Sokoban, NP-hard in the non-planar case, see this Q&A on cstheory).

If you have many, group them by topic.

[1] Robert A. Hearn, Erik D. Demaine: Games, puzzles and computation. A K Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237

Answer 1

Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known that there are positions that require exponential moves, but the problem is only known to be $NP$-hard.

http://arxiv.org/abs/1409.1530

https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach

Answer 2

I'm not sure if this fits your notion of restriction, but here goes.

The "Minimum QBF-oracle Circuit Size Problem": given the truth table of a Boolean function and parameter k, is there a circuit of size at most k computing the function over the basis AND, OR, NOT, and QBF? (A QBF gate interprets its input string as a fully quantified Boolean formula F, and the output is 1 iff F is true.)

The problem is definitely in PSPACE, known to be complete under ZPP reductions, but not known for deterministic polynomial time reductions. Provably not PSPACE-complete under logspace reductions! See Allender, Holden, and Kabanets.

Answer 3

The following problem matches the requirement somehow twofold...

Containment of regular expressions, that is, testing whether the language of a regular expressions $r$ is contained in the language of a regular expression $r'$ (i.e., whether $L(r)\subseteq L(r')$) is a well-known PSPACE-complete problem, even if $r$ is chosen as $\Sigma^*$ (then it is called Universality of regular expressions).

Similarly, Equivalence of regular expressions asks whether $L(r)=L(r')$ and is PSPACE-complete (hardness following from Universality).

However, the picture becomes less clear for chain regular expressions: They are of the general form $r_1\cdots r_n$ (therefore: chain) with only restricted factors $r_i$. A factor can be of the form $e=(w_1+\ldots+w_m)$ where each $w_j$ is a string or $e^*$ or $e^+$ or $e?$ with the same kind of $e$. An example is $a(b+cd)(ab+cde+f)^*d?$.

Containment of chain regular expressions is still PSPACE-complete but Equivalence of chain regular expressions is unclear (although known to be coNP-hard and in PSPACE).

By the way, the PSPACE-upper bound easily follows by translating the expressions into NFAs and nondeterministically searching for a counter-example: guess a string letter by letter and keep track of the state sets that can be reached in the NFAs.

Answer 4

games with just 2-buttons and 2-doors in which all doors are initially closed:

"Levels" are finite subgraphs of the planar grid. $\:$ Vertices are identified as one of [start,button,empty,door,finish]. $\:$ Each door vertex has a set of opening buttons and a set of closing buttons. $\:$ A k-door is a door that's controlled by at most k buttons, and a a k-button is a button that controls at most k doors. $\:$ Whenever on a button vertex, one can press the button, which opens the doors that the button is an opening button for and closes the doors that the button is a closing button for. $\:$ The goal is to get from the start vertex to the end vertex without going on closed doors.


Such levels can clearly be solved in FPSPACE, and solving them is FNPSPACE-hard
even when [each door has exactly one opening button and exactly one closing button]
and [each button opens exactly one door and closes exactly one door].
On the other hand, this paper states that "It is an open problem whether a game with
2-buttons and 2-doors remains PSPACE-hard when all doors are initially closed."


FNPSPACE-hardness when all doors are initially closed will be recovered if the exactly-one-of-each conditions from my previous paragraph are modified in either of the following ways:

allow doors to have 2 opening buttons (in addition to 1 closing button)
or
allow buttons to close 2 doors (in addition to opening 1 door)

.


Page 10 of this paper shows that determining solvability is NC1-hard even with no buttons and
no doors. $\:$ Otherwise, I do not know of any hardness results for solving levels with 2-buttons
and 2-doors when all doors are initially closed (even without the exactly-one-of-each conditions).