EXPSPACE-complete problems

Question

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up.

So far, I found these, and I have trouble expanding the list:

• universality (or other properties) of regular expressions with exponentiation.
• problems related to vector addition systems
• unobservable games (see for instance this blog)
• some fragment of FO-LTL, in On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics

Do you know other contexts when EXPSPACE-completeness appears naturally?

Answer 1

Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). Many natural problems in computational algebraic geometry end up being equivalent to one of these problems. Also see the Bayer–Mumford survey "What can be computed in algebraic geometry?"

Answer 2

Many problems that are PSPACE-complete become EXPSPACE-complete when the input is given "succinctly", i.e., via some encoding that lets you describe inputs that would normally be of exponential size.

Here is an example on finite automata (equivalently, on directed graphs with labeled edges): deciding whether two automata accept the same language (have the same set of labeled paths from an origin to a destination node) is PSPACE-complete. If the automata (graphs) are given by Boolean formulae (nodes are valuations v,v',.. and there are Boolean formulae telling whether v-a->v' is an edge), the problem becomes EXPSPACE-complete. NB: there are many other ways of defining succinctly a large graph/automaton, see e.g. this paper.

The example with regular expressions fits this pattern. Introducing a "..^2" notation for squaring lets you write compactly regular expressions that would be very large if you were to expand each "(foo)^2" by "foo foo", and "((bar)^2)^2" by "bar bar bar bar". Naturally, some problems that are PSPACE-complete without squaring become EXPSPACE-complete with squaring allowed, here is the classic reference. [NB: Other examples, like regular expressions with intersection or with complements do not obviously fit the pattern of new notation that expands into exponentially larger input in standard notation.]

Similarly, a LOGSPACE-complete problem (e.g., reachability in directed graphs) may become EXPSPACE-complete if your succinct encoding allows for the description of graphs of doubly exponential size.

Bottom line: you can easily come up with new, albeit perhaps artificial, EXPSPACE-complete problems, by considering classic PSPACE or LOGSPACE problems (of which you'll find many) and allowing for compact/succinct/.. encoding of the input.

Answer 3

Temporal Planning with concurrent actions is EXPSPACE-complete, as shown in

J. Rintanen, “Complexity of Concurrent Temporal Planning,” Proceedings of the 17th International Conference on Automated Planning and Scheduling, pp. 280–287, 2007

The problem is roughly the following (beware in the paper above it is defined in a different but equivalent way). Let $A$ be a finite set of propositional variables and $O$ a finite set of actions, where each action is $o=(d,P_s,P_e,P_o,E_s,E_e)$, where:

• $d\in\mathbb{N}$ is the time duration of the action.
• $P_s$, $P_e$ and $P_o$ are the action preconditions, which are propositional formulae over $A$ that must be true respectively at the beginning, at the end, and over all the execution of the action for it to be applicable.
• $E_s$ and $E_e$ are sets of literals over $A$ which specify the begin and end effects (i.e., how the action affects the state variables).

The problem is, given a valuation of the state variables $I$ that describes the initial state, and a propositional formula $G$ that describes the goal condition, to find if there exist a way of arranging actions, possibly overlapping in time, such that, if applied from $I$, lead to a state where $G$ holds.

Note that following the proof one might argue that the EXPSPACE-completeness comes again from the succinctness of the $d$ numeric input (but not only that, anyway), but a unary input would be very unnatural, so I feel this is a problem which is naturally EXPSPACE-complete.

Answer 4

Most standard classes from PSPACE on (well, even for NP, if you like) have some tiling problem as a complete problem. Such tiling problems are not so far from the natural Turing machine based complete problems, but they are often quite convenient as a starting point for reductions. In a nutshell, a tiling problem gives you a set of allowed tiles (that is: tile types from which you can use as many tiles as you like) and rules how they can be combined, often by a set H of horizontally allowed pairs of tiles and a set V of vertically allowed types. Furthermore, a first tile and a last tile can be given and, depending on the actual version, and how many rows and/or columns the tiling should have. The algorithmic question is, whether there exists a correct tiling, that is, an assignment of positions to tiles, that obeys all constraints and has the start tile in the lower left position and the last tile in the upper right position. (There are many variations as to the exact definitions).

For the class at hand, EXPSPACE, you can choose between (at least) two versions:

• exponential width corridor tiling, where a parameter n is given and the question is whether there is a tiling with 2^n columns and any number of rows
• exp-times-exp tiling game, where, given n, the tiling shall be of size 2^n times 2^n, where the first players goal is to reach a correct tiling and the second player tries to prevent that.

Papers to look at for this are - Bogdan S. Chlebus: "Domino-Tiling Games". J. Comput. Syst. Sci. 32(3): 374-392 (1986) - Peter van Emde Boas: "The convenience of tilings", in: Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, Vol. 187, 1997, pp. 331-363.

Answer 5

an example & proof is given in Introduction to Automata Theory, Languages, and Computation Hopcroft/ Ullman Thm13.16 that any nondeterministic algorithm for the first-order theory of reals with addition is NExpTime-hard. therefore it is presumably also NExpSpace-hard unless some theoretical breakthrough proves it can be solved "in tighter space" but of course that question is similar (nearly identical?) to L=?P. (in other words all the known NExpTime-hard problems are also basic candidates for NExpSpace-hard, and if any provably arent, it would likely mean a breakthrough resolution of a long-open complexity class separation.) the proof comes from Fischer, Rabin 1974, "Super-exponential complexity of Presburger arithmetic," Complexity of Computation (R. Karp ed.). Proceedings of SIAM-AMS Symposium in Applied Mathematics.