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

<p>On the contrary, if a TM uses exponential space it can still run in doubly-exponential time, <em>e.g.</em> 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. </p>

<p>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 <em>double</em> exponential since $\mathsf{EXPSPACE} \subseteq 2 \mathsf{EXPTIME}$). I don’t have a specific example problem in mind though.</p>

CC BY-SA 3.0
2018-03-01T02:32:08.907Z
Thank you very much! I hadn't considered classes larger than EXPSPACE. It seems so obvious now. =]
Jango
CC BY-SA 3.0
2018-03-01T02:33:46.313Z
There's always a bigger class ;)
Nicola Gigante
CC BY-SA 3.0
2018-03-01T01:08:39.787Z
2018-03-01T02:35:35.843Z
2018-03-01T02:35:35.843Z
Nicola Gigante
<p>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?</p>

<p><img src="https://plato.stanford.edu/entries/computational-complexity/fig2.png" alt=""></p>

CC BY-SA 3.0
2018-03-01T02:51:25.710Z
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...
Joshua Grochow
CC BY-SA 3.0
2018-03-01T03:17:33.280Z
You are right, I was confusing upper and lower bounds. Thank you for your comment.
Jango
<cc.complexity-theory><complexity-classes><polynomial-hierarchy>
What are the problems in EXPSPACE \ EXPTIME?
Jango
# What are the problems in EXPSPACE \ EXPTIME?

(Asked by: username_0 on 2018-03-01)

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?

![](https://plato.stanford.edu/entries/computational-complexity/fig2.png)

**Tags:** cc.complexity-theory, complexity-classes, polynomial-hierarchy
> **Comments:**
> **username_1**: 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...  
> **username_0**: You are right, I was confusing upper and lower bounds. Thank you for your comment.  

---

## 1 answers

### Answer by username_2 on 2018-03-01. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you very much! I hadn't considered classes larger than EXPSPACE. It seems so obvious now. =]  
> **username_2**: There's always a bigger class ;)  

---

