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:

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

  • 2
    The decision problem for the theory of real-closed fields is claimed to be EXPSPACE-complete in 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 (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 Oct 22 '14 at 19:30
  • 6
    Anyway, what kind of an answer to “are there really so few of them” do you expect other than opinionated speculation? – Emil Jeřábek Oct 22 '14 at 20:04
  • @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 Oct 23 '14 at 7:42
  • 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 Oct 23 '14 at 15:03
  • the question is not "are they rare" it is "can you find others that those listed?" I'll edit to make it clearer – Denis Oct 23 '14 at 15:04
up vote 22 down vote accepted

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?"

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.

  • 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 Oct 23 '14 at 13:16
  • 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 Oct 23 '14 at 13:29
  • 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 Oct 23 '14 at 16:13

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.

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.

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.

  • 5
    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 Oct 24 '14 at 7:23
  • 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 Oct 24 '14 at 23:28

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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