<p>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.</p>

<p><a href="http://arxiv.org/abs/1409.1530" rel="nofollow noreferrer">http://arxiv.org/abs/1409.1530</a></p>

<p><a href="https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach">https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach</a></p>

CC BY-SA 3.0
2015-03-09T12:09:13.417Z
2015-03-09T12:09:13.417Z
2017-04-13T12:57:54.777Z
Tom van der Zanden
<p>I'm not sure if this fits your notion of restriction, but here goes. </p>

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

<p>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 <a href="http://eccc.hpi-web.de/report/2014/176/">Allender, Holden, and Kabanets</a>.</p>

CC BY-SA 3.0
2015-03-10T02:21:56.717Z
2015-03-10T05:19:30.313Z
2015-03-10T05:19:30.313Z
Ryan Williams
<p>The following problem matches the requirement somehow twofold...</p>

<p><em>Containment of regular expressions</em>, 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 <em>Universality</em> of regular expressions). </p>

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

<p>However, the picture becomes less clear for <em>chain regular expressions</em>: 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?$.</p>

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

<p>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. </p>

CC BY-SA 3.0
2015-03-10T06:43:48.697Z
2015-03-10T06:43:48.697Z
Thomas S
<p>What are problems with the following properties:</p>

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

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

<p>Four examples from "puzzles &amp; C.":</p>

<ul>
<li>The complexity of 1x1 Rush Hour [1] (PSPACE-complete for blocks of size 2x1 );</li>
<li>[<strong>SOLVED</strong>] The complexity of planar Subway Shuffle [1] (PSPACE-complete even for planar graphs, a draft of the paper can be <a href="http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/" rel="nofollow noreferrer">downloaded here</a> );</li>
<li>The complexity of Lunar-Lockout without fixed blocks [1] (PSPACE-complete with fixed blocks);</li>
<li>(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 <a href="https://cstheory.stackexchange.com/q/9387/3247">this Q&amp;A on cstheory</a>).</li>
</ul>

<p>If you have many, group them by topic.</p>

<p>[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</p>

CC BY-SA 3.0
2015-03-09T11:14:07.297Z
Almost every PSPACE-complete problem have many special cases no one have bothered studying. How do you define *open problem*?
R B
CC BY-SA 3.0
2015-03-09T11:38:12.273Z
@RB: "open problem" a problem that is currently being studied (or has being studied, cited a few times, ...) and researchers think it would be interesting to solve  (at least to shape the boundary of PSPACE-complete problems ... under the shadow of the P vs PSPACE daemon :-).
Marzio De Biasi
CC BY-SA 3.0
2015-03-09T12:28:00.067Z
TAUT is a restricted version of QBF, and it is an open problem whether it is PSPACE- or NP-hard, so it meets all requirements, but somehow I don’t think it is in the right spirit.
Emil Jeřábek
CC BY-SA 3.0
2015-03-09T13:26:24.637Z
@EmilJeřábek: QBF restricted to a finite number of quantifiers could be in the spirit (i.e. PH vs PSPACE) ... but it is a jump from "infinite to finite"; I'm more interested in restrictions on the finite "structures" of the problem.
Marzio De Biasi
<big-list><open-problem>
Problems not known to be PSPACE-complete
Marzio De Biasi
# Problems not known to be PSPACE-complete

(Asked by: username_0 on 2015-03-09)

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](http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/) );
* 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](https://cstheory.stackexchange.com/q/9387/3247)).

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

**Tags:** big-list, open-problem
> **Comments:**
> **username_1**: Almost every PSPACE-complete problem have many special cases no one have bothered studying. How do you define *open problem*?  
> **username_0**: @RB: "open problem" a problem that is currently being studied (or has being studied, cited a few times, ...) and researchers think it would be interesting to solve  (at least to shape the boundary of PSPACE-complete problems ... under the shadow of the P vs PSPACE daemon :-).  
> **username_2**: TAUT is a restricted version of QBF, and it is an open problem whether it is PSPACE- or NP-hard, so it meets all requirements, but somehow I don’t think it is in the right spirit.  
> **username_0**: @EmilJeřábek: QBF restricted to a finite number of quantifiers could be in the spirit (i.e. PH vs PSPACE) ... but it is a jump from "infinite to finite"; I'm more interested in restrictions on the finite "structures" of the problem.  

---

## 3 answers

### Answer by username_3 on 2015-03-09. Score: 12

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 by username_4 on 2015-03-10. Score: 11

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](http://eccc.hpi-web.de/report/2014/176/).


---

### Answer by username_5 on 2015-03-10. Score: 5

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.


---

