12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Almost every PSPACE-complete problem have many special cases no one have bothered studying. How do you define open problem? $\endgroup$ – R B Mar 9 '15 at 11:14
  • $\begingroup$ @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 :-). $\endgroup$ – Marzio De Biasi Mar 9 '15 at 11:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek supports Monica Mar 9 '15 at 12:28
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Mar 9 '15 at 13:26
11
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (Not related to this answer, but anyway,) ​ How do we know that the 7-dominating set "problem on n node graphs can be solved in" n$^{7+o(1)}$ time? ​ ​ ​ Reference 17 only makes that claim for ​ $\ell$ ≥ 8 . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Dec 17 '15 at 10:27
  • $\begingroup$ (I should've mentioned this earlier, but) I have now about a question about the k=7 case on this site. ​ ​ $\endgroup$ – user6973 Dec 21 '15 at 11:15
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you have a simple proof or reference for the hardness of the sign-opposed version (where each buttons opens one door and closes another, and each door is opened by one button and closed by another)? $\endgroup$ – Jonas Kölker Mar 27 '17 at 9:11
  • $\begingroup$ No, although I realize I know how to show hardness even when all doors start closed, which I'll probably publish this year. ​ ​ $\endgroup$ – user6973 Mar 27 '17 at 22:03
  • $\begingroup$ I think I have an idea for how to do it as well. Would you send me a copy of your manuscript when you get it accepted? I'd love to compare ideas :-) [re: the sign-opposed hardness, IINM the reduction in the Bloxorz paper is sign-opposed on both doors and buttons.] $\endgroup$ – Jonas Kölker Mar 28 '17 at 11:10
  • $\begingroup$ Yes. ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Mar 29 '17 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.