0
$\begingroup$

Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial bounded space and problems that are only solvable in exponential bounded space. These latter problems are outside PSPACE, so they must be either inside EXPTIME or outside of it. The ones inside are problems that need exponential time to be solved, but not necessarily exponential space. The ones outside are problems that require exponential space to be solved and, since a machine can only do a constant number of movements per transition, they also require exponential time. So my question is: shouldn't this put them all back inside EXPTIME? It doesn't make sense to me that there are problems inside EXSPACE but outside EXPTIME, i.e. problems that require exponential space without requiring exponential time. What are the problems in EXPSPACE outside EXPTIME?

$\endgroup$
  • 1
    $\begingroup$ You seem to be confusing upper & lower bounds. E.g. if a problem "needs" exp space, then it can't be solved using subexp space. An algorithm that uses exp space takes $\geq$ exp time, but that means that exp-time is a lower bound, whereas being in EXP is an upper bound. Also, your arguments (as stated) seem to be mixing up deterministic and nondeterministic exponential time... To answer your question, if $EXPSPACE \neq NEXP$ then any EXPSPACE-complete problem would be an answer, such as the Ideal Membership Problem. As stated, I don't think this question is research-level though... $\endgroup$ – Joshua Grochow Mar 1 '18 at 2:51
  • $\begingroup$ You are right, I was confusing upper and lower bounds. Thank you for your comment. $\endgroup$ – Jango Mar 1 '18 at 3:17
5
$\begingroup$

Your argument proves that $\mathsf{NEXPTIME}\subseteq\mathsf{EXPSPACE}$, since if a TM terminates in (nondeterministic) exponential time it cannot write to more than an exponential number of tape cells.

On the contrary, if a TM uses exponential space it can still run in doubly-exponential time, e.g. a TM that increments a binary counter of $2^n$ bits until wrapping uses exponential space but runs in $\mathcal{O}(2^{2^n})$ steps.

So the problems that you’re looking for are those that require at most exponential space but whose running time cannot be bounded by an exponential (even though it can be bounded by a double exponential since $\mathsf{EXPSPACE} \subseteq 2 \mathsf{EXPTIME}$). I don’t have a specific example problem in mind though.

$\endgroup$
  • $\begingroup$ Thank you very much! I hadn't considered classes larger than EXPSPACE. It seems so obvious now. =] $\endgroup$ – Jango Mar 1 '18 at 2:32
  • 1
    $\begingroup$ There's always a bigger class ;) $\endgroup$ – gigabytes Mar 1 '18 at 2:33

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.