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

<p>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. <a href="http://dx.doi.org/10.1007/3-540-48523-6_14">this paper</a>.</p>

<p>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 <a href="http://dx.doi.org/10.1109/SWAT.1972.29">the classic reference</a>. [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.]</p>

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

<p><strong>Bottom line:</strong> 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.</p>

CC BY-SA 3.0
2014-10-23T13:16:29.317Z
Indeed, this is kind of "cheating", I am looking for more natural ones. The intermediary case is when the input contains just one integer (likes PRIMES), and possibly something else like a formula, which is the case which interests me. I actually showed EXPSPACE-comlpeteness for a problem like this, which is borderline in the category you describe.
Denis
CC BY-SA 3.0
2014-10-23T13:29:03.747Z
because if you have an integer in the input, encoding it in binary is the most natural way, and not in unary to artificially reduce the complexity.
Denis
CC BY-SA 3.0
2014-10-23T16:13:42.153Z
More than a "natural" problem, you need one that is easy to encode in the kind of reduction you are trying to achieve. This usually means "close to your original problem under consideration". The more choices you have, the more likely you are to find something quite close.
phs
CC BY-SA 3.0
2014-10-23T09:42:14.257Z
2014-10-23T10:21:53.733Z
2014-10-23T10:21:53.733Z
phs
<p>Temporal Planning with concurrent actions is EXPSPACE-complete, as shown in </p>

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

<p>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 <em>actions</em>, where each action is $o=(d,P_s,P_e,P_o,E_s,E_e)$, where:</p>

<ul>
<li>$d\in\mathbb{N}$ is the time duration of the action.</li>
<li>$P_s$, $P_e$ and $P_o$ are the action <em>preconditions</em>, 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.</li>
<li>$E_s$ and $E_e$ are sets of literals over $A$ which specify the
begin and end <em>effects</em> (<em>i.e.</em>, how the action affects the state 
variables).</li>
</ul>

<p>The problem is, given a valuation of the state variables $I$ that describes the initial state, and a propositional formula $G$ that describes the <em>goal condition</em>, 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.</p>

<p>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 <em>naturally</em> EXPSPACE-complete.</p>

CC BY-SA 3.0
2016-06-07T12:47:02.207Z
2016-08-28T08:23:00.363Z
2016-08-28T08:23:00.363Z
Nicola Gigante
<p>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).</p>

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

<ul>
<li>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</li>
<li>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.</li>
</ul>

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

CC BY-SA 3.0
2016-09-02T21:59:23.287Z
2016-09-02T21:59:23.287Z
Thomas S
<p>an example &amp; 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 <a href="https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems">NExpTime-hard problems</a> 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," <em>Complexity of Computation</em> (R. Karp ed.). Proceedings of SIAM-AMS Symposium in Applied Mathematics.</p>

CC BY-SA 3.0
2014-10-24T07:23:10.763Z
The question asks for EXPSPACE-complete problems and you have given a bunch of problems that are hard for other complexity classes, which are all believed to be distinct from EXPSPACE. You don't even mention EXPSPACE. Why?
David Richerby
CC BY-SA 3.0
2014-10-24T23:28:21.043Z
as stated, ***candidates*** / research leads, & also some pov on the original question of why such problems might be "rare" in that their existence may be tied to open complexity class separations. for anyone who has looked the proofs for NExpSpace-complete and NExpTime-hard problems are very similar & it would be interesting to pinpoint why NExpTime proofs are not also sufficient for the property of NExpSpace complete (if it can actually be done given current knowledge)
vzn
CC BY-SA 3.0
2014-10-24T03:40:13.310Z
2014-10-24T03:40:13.310Z
2017-04-13T12:32:28.117Z
vzn
<p>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 (<a href="http://dx.doi.org/10.1016/0001-8708(82)90048-2">Mayr&ndash;Meyer</a> and <a href="http://dx.doi.org/10.1007/BFb0029002">Mayr</a>) and hence the computation of Gr&ouml;bner bases. This was then extended to the computation of syzygies (<a href="http://dx.doi.org/10.1016/S0747-7171(88)80039-7">Bayer and Stillman</a>). Many natural problems in computational algebraic geometry end up being equivalent to one of these problems. Also see the <a href="http://arxiv.org/abs/alg-geom/9304003">Bayer&ndash;Mumford survey "What can be computed in algebraic geometry?"</a></p>

CC BY-SA 3.0
2016-08-29T10:02:16.513Z
The ideal membership problem is also related to the *coverability problem* in *vector addition systems*, see Lipton (1976, http://www.cs.yale.edu/publications/techreports/tr63.pdf) for the lower bound and Rackoff (1978, http://dx.doi.org/10.1016/0304-3975(78)90036-1) for the upper bound.
Sylvain
CC BY-SA 3.0
2014-10-23T17:27:26.683Z
2014-10-23T19:31:54.720Z
2014-10-23T19:31:54.720Z
Joshua Grochow
<p>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.</p>

<p>So far, I found these, and I have trouble expanding the list:</p>

<ul>
<li>universality (or other properties) of regular expressions with exponentiation.</li>
<li>problems related to vector addition systems</li>
<li>unobservable games (see for instance <a href="http://teytaud.over-blog.com/article-on-the-complexity-of-games-51881321.html" rel="nofollow noreferrer">this blog</a>)</li>
<li>some fragment of FO-LTL, in <a href="http://www.inf.kcl.ac.uk/staff/kuag/publi/complexity.ps" rel="nofollow noreferrer">On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics</a></li>
</ul>

<p>Do you know other contexts when EXPSPACE-completeness appears naturally?</p>

CC BY-SA 3.0
2014-10-22T19:30:33.623Z
The decision problem for the theory of real-closed fields is claimed to be EXPSPACE-complete in http://www.sciencedirect.com/science/article/pii/S0747717188800063 , though I have a hard time figuring out how is the hardness part supposed to follow from the given reference (http://www.sciencedirect.com/science/article/pii/0001870882900482). Presburger arithmetic and the theory of reals with addition are complete for alternating exponential time with polynomially many alternations (due to Berman), which is a close miss (EXPSPACE is the same without the bound on alternations).
Emil Jeřábek
CC BY-SA 3.0
2014-10-22T20:04:29.480Z
Anyway, what kind of an answer to “are there really so few of them” do you expect other than opinionated speculation?
Emil Jeřábek
CC BY-SA 3.0
2014-10-23T07:42:48.573Z
@EmilJeřábek I am mainly checking whether I missed some of them in my search. Indeed, some seem to be harder to find, like the one I mention in the update.
Denis
CC BY-SA 3.0
2014-10-23T15:03:32.293Z
agreed they do not seem common in the literature & also agreed with EJ that the question of their "rarity" is not very well defined. it is possible they are not studied as much because they are intractable by defn. whereas eg on other hand NP hard/complete problems are not _("yet")_ proven intractable. (P vs NP)
vzn
CC BY-SA 3.0
2014-10-23T15:04:45.797Z
the question is not "are they rare" it is "can you find others that those listed?" I'll edit to make it clearer
Denis
CC BY-SA 3.0
2014-10-23T20:26:52.790Z
see also [NExp-Complete](http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems) problems, tcs.se. (ofc Exp=?NExp is equiv to P=?NP)
vzn
CC BY-SA 4.0
2021-09-22T15:29:54.170Z
You mention problems related with VASS. Which problems are EXPSPACE-complete in particular? Do you have a reference?
Nicola Gigante
CC BY-SA 4.0
2021-10-01T15:16:02.253Z
@gigabytes Yes for instance this paper: https://arxiv.org/abs/1301.4874
Denis
<cc.complexity-theory><reference-request><big-list>
EXPSPACE-complete problems
Denis
# EXPSPACE-complete problems

(Asked by: username_0 on 2014-10-22)

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](http://teytaud.over-blog.com/article-on-the-complexity-of-games-51881321.html))
* some fragment of FO-LTL, in [On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics](http://www.inf.kcl.ac.uk/staff/kuag/publi/complexity.ps)

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

**Tags:** cc.complexity-theory, reference-request, big-list

> **Comments:**
> **username_1**: The decision problem for the theory of real-closed fields is claimed to be EXPSPACE-complete in http://www.sciencedirect.com/science/article/pii/S0747717188800063 , though I have a hard time figuring out how is the hardness part supposed to follow from the given reference (http://www.sciencedirect.com/science/article/pii/0001870882900482). Presburger arithmetic and the theory of reals with addition are complete for alternating exponential time with polynomially many alternations (due to Berman), which is a close miss (EXPSPACE is the same without the bound on alternations).  
> **username_1**: Anyway, what kind of an answer to “are there really so few of them” do you expect other than opinionated speculation?  
> **username_0**: @EmilJeřábek I am mainly checking whether I missed some of them in my search. Indeed, some seem to be harder to find, like the one I mention in the update.  
> **username_2**: agreed they do not seem common in the literature & also agreed with EJ that the question of their "rarity" is not very well defined. it is possible they are not studied as much because they are intractable by defn. whereas eg on other hand NP hard/complete problems are not _("yet")_ proven intractable. (P vs NP)  
> **username_0**: the question is not "are they rare" it is "can you find others that those listed?" I'll edit to make it clearer  
> **username_2**: see also [NExp-Complete](http://cstheory.stackexchange.com/questions/3297/nexp-complete-problems) problems, tcs.se. (ofc Exp=?NExp is equiv to P=?NP)  
> **username_3**: You mention problems related with VASS. Which problems are EXPSPACE-complete in particular? Do you have a reference?  
> **username_0**: @gigabytes Yes for instance this paper: https://arxiv.org/abs/1301.4874  

---

## 5 answers

### Answer by username_7 on 2014-10-23. Score: 25 | Accepted answer

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](http://dx.doi.org/10.1016/0001-8708(82)90048-2) and [Mayr](http://dx.doi.org/10.1007/BFb0029002)) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies ([Bayer and Stillman](http://dx.doi.org/10.1016/S0747-7171(88)80039-7)). 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?"](http://arxiv.org/abs/alg-geom/9304003)

> **Comments:**
> **username_8**: The ideal membership problem is also related to the *coverability problem* in *vector addition systems*, see Lipton (1976, http://www.cs.yale.edu/publications/techreports/tr63.pdf) for the lower bound and Rackoff (1978, http://dx.doi.org/10.1016/0304-3975(78)90036-1) for the upper bound.  

---

### Answer by username_4 on 2014-10-23. Score: 20

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 grausername_4 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 (grausername_4) 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](http://dx.doi.org/10.1007/3-540-48523-6_14).

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](http://dx.doi.org/10.1109/SWAT.1972.29). [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 grausername_4) may become EXPSPACE-complete if your succinct encoding allows for the description of grausername_4 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.

> **Comments:**
> **username_0**: Indeed, this is kind of "cheating", I am looking for more natural ones. The intermediary case is when the input contains just one integer (likes PRIMES), and possibly something else like a formula, which is the case which interests me. I actually showed EXPSPACE-comlpeteness for a problem like this, which is borderline in the category you describe.  
> **username_0**: because if you have an integer in the input, encoding it in binary is the most natural way, and not in unary to artificially reduce the complexity.  
> **username_4**: More than a "natural" problem, you need one that is easy to encode in the kind of reduction you are trying to achieve. This usually means "close to your original problem under consideration". The more choices you have, the more likely you are to find something quite close.  

---

### Answer by username_3 on 2016-06-07. Score: 6

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 by username_5 on 2016-09-02. Score: 5

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 by username_2 on 2014-10-24. Score: -8

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](https://cstheory.stackexchange.com/questions/3297/nexp-complete-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.

> **Comments:**
> **username_6**: The question asks for EXPSPACE-complete problems and you have given a bunch of problems that are hard for other complexity classes, which are all believed to be distinct from EXPSPACE. You don't even mention EXPSPACE. Why?  
> **username_2**: as stated, ***candidates*** / research leads, & also some pov on the original question of why such problems might be "rare" in that their existence may be tied to open complexity class separations. for anyone who has looked the proofs for NExpSpace-complete and NExpTime-hard problems are very similar & it would be interesting to pinpoint why NExpTime proofs are not also sufficient for the property of NExpSpace complete (if it can actually be done given current knowledge)  

---

