<p>Depends what you mean by "class". </p>

<p>I don't know of any natural class that satisfies that, but certainly one can do the following:</p>

<p>Consider the set of languages that are decidable in time $2^n$ (exactly, not just any exponential). This is strictly contained in EXP by the time-hierarchy theorem.
Take the union of this set and PSPACE, and you have a class that strictly contains P (again, time hierarchy), contains PSPACE, and is contained in EXP (and presumably, if PSPACE$\neq$ EXP, then there is also strict containemnt here).</p>

CC BY-SA 3.0
2017-09-01T13:41:21.743Z
2017-09-01T13:41:21.743Z
Shaull
<p>It is consistent with current state of knowledge that PSpace=ExpTime. Therefore there are no classes that we know that falls strictly between them.</p>

<p>If they are not equal there are infinite number of classes between them by diagonalization (Ladner's theorem).</p>

<p>If you are looking for well known classes that we know contain PSpace and are contained in ExpTime you can check complexity zoo. Based on <a href="https://www.math.ucdavis.edu/~greg/zoology/diagram.xml" rel="nofollow noreferrer">zoology</a> <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rg" rel="nofollow noreferrer">RG</a> is an example. Other than that there doesn't seem to be any class with name that falls between them.</p>

CC BY-SA 3.0
2017-09-04T21:16:27.073Z
2017-09-05T03:18:53.453Z
2017-09-05T03:18:53.453Z
Kaveh
<p>I can show two ways (of course I don't claim that they are the only options):</p>

<ol>
<li><p>Generalize <a href="https://cstheory.stackexchange.com/users/7531/shaull">Shaull</a>'s answer and take $\mathsf{PSPACE\cup DTIME}(2^{O(n^k)})$ for some fixed $k$.</p></li>
<li><p>But you may be interested in another variant. You can take $f(n)$ such that $f(n)\in O(2^{n^k})\cap\omega(poly(n))$ for some fixed $k$. Under assumption that $\mathsf{EXP\not\subset DSPACE}(f(n))$ you just take a complexity class $\mathsf{DTISP}(exp,f(n))$. The difference between this and $\mathsf{DSPACE}(f(n))\cap \mathsf{EXP}$ is that former requires the same algorithm to run in exponential time and $f(n)$ space. Latter only requires separate algorithms to do these things separately. It will contain $\mathsf{PSPACE}$ and be contained in $\mathsf{EXP}$. For example you can replace $(f(n))$ with $qpoly$ (quasipolynomial) and get $\mathsf{DTISP}(exp,qpoly)$.</p></li>
</ol>

<p>P.S. They all are provably larger than $\mathsf P$. Because you are asking about a class that is strictly larger than $\mathsf{PSPACE}$ under assumption $\mathsf{PSPACE\ne EXP}$. Under the same assumption it will also strictly contain $\mathsf{P}$. Under opposite assumption of $\mathsf{PSPACE=EXP}$ we know that $\mathsf{P\ne PSPACE}$ (due to time hierarchy theorem) and since that class is at least as large as $\mathsf{PSPACE}$, it will strictly contain $\mathsf P$ as well.</p>

<p>Edit: missed that you already suggested that complexity class in question. So, replaced it.</p>

CC BY-SA 3.0
2017-09-04T10:40:39.203Z
2017-09-04T19:37:36.223Z
2017-09-04T19:37:36.223Z
rus9384
<p>1) What classes contain $\textbf{PSPACE}$, are contained in $\textbf{EXP}$ and (presumably) are not equal to $\textbf{PSPACE}$ nor to $\textbf{EXP}$?</p>

<p>A possible class satisfying this requirement: the class of languages that can be recognized in exponential time and subexponential memory.</p>

<p>2) Which of these classes are provably strictly larger than $\textbf{P}$?</p>

CC BY-SA 3.0
2017-09-01T18:42:08.747Z
Similar to your example, you could consider the class of languages that can be decided by an alternating Turing machine that runs in subexponential time using polynomial space.
Michael Wehar
CC BY-SA 3.0
2017-09-01T18:47:42.990Z
Because PSPACE = AP and APSPACE = EXP, you could alternatively think of this as trying to find a class between AP and APSPACE.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-01T18:55:45.033Z
Thinking about it a little differently, there might be some natural classes between PSPACE and APSPACE.  Adding a fixed number of alternations doesn't break out of PSPACE, but if you allow the number of alternations to be bounded by some function of n, then you will be between PSPACE and APSPACE.
Michael Wehar
CC BY-SA 3.0
2017-09-01T19:33:55.490Z
I find these kinds of fundamental problems on time vs space to be very interesting.  If you would ever like to chat about this, please let me know.  Thank you again for posting this question!
Michael Wehar
CC BY-SA 3.0
2017-09-01T19:40:50.553Z
Also, you could consider problems that are polynomial space verifiable with subexponential witness sizes.
Michael Wehar
CC BY-SA 3.0
2017-09-04T18:50:18.777Z
@MichaelWehar, what that function would be? $\log^k n$?
rus9384
CC BY-SA 3.0
2017-09-05T03:04:19.053Z
@rus9384 Hi there!  Not sure if I understand you question.  Could you possibly clarify your question further?  :)
Michael Wehar
CC BY-SA 3.0
2017-09-05T03:07:00.613Z
@MichaelWehar, if you'll take $O(\log n)$ it still is in $\mathsf{PSPACE}$.
rus9384
CC BY-SA 3.0
2017-09-05T03:07:57.353Z
@rus9384 I'm not quite sure what you are suggesting to be $O(\log(n))$.
Michael Wehar
CC BY-SA 3.0
2017-09-05T03:13:18.217Z
@MichaelWehar, number of alternations. In fact, if number of alternations is $f(n)$ then the equivalent class is $DTISP(exp,2^{f(n)})$, for any $f(n)\in\Omega(\log n)$.
rus9384
CC BY-SA 3.0
2017-09-05T03:29:10.870Z
@rus9384 So the classic result is that $DTIME(f(n))$ is a subset of $ASPACE(\log(f(n)))$.  I don't see how we can modify the proof to get that $DTISP(2^n, 2^{f(n)})$ is a subset of $\Sigma^{f(n)}SPACE(poly(n))$.
Michael Wehar
CC BY-SA 3.0
2017-09-05T03:32:13.113Z
The point with the proof is that you have a large number of alternations, but each quantifier is "thin" in the sense that few bits are quantified over for each alternation.  We could "slightly" reduce the number of alternations by making the quantifiers less thin, but I don't see how to get your result.  If you have a proof, please do share as I'm very interested in this subject!  Again, it is possible that I missed something.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-05T16:21:37.327Z
@rus9384 Hi again, just wanted to follow-up and see what you think about my response.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-05T23:13:17.060Z
@MichaelWehar, it is subset, proof is similar to proof $\mathsf{EXP=APSPACE}$. Harder part is to prove that opposite is true. You will need to reuse the space (that's why under assumption of $\mathsf{P = NP\ne PSPACE}$ TQBF with $f(n)$ quantifiers is not solvable in $2^{f(n)}$ time, only in $n^{f(n)}$ - time can't be reused).
rus9384
CC BY-SA 3.0
2017-09-06T01:48:34.093Z
@rus9384 Thank you very much for the reply!!  But, I just don't see it.  In the $EXP$ subset $APSPACE$ proof, you use exponentially many alternations.  It doesn't seem trivial to generalize this as you suggested as each alternation corresponds with one step of the computation.  But, here we are not reducing the number of steps, rather we are reducing the space.
Michael Wehar
CC BY-SA 3.0
2017-09-06T01:48:44.860Z
@rus9384 Could you possible write up your proof??  :)
Michael Wehar
CC BY-SA 3.0
2017-09-06T01:57:08.397Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/65155/discussion-between-rus9384-and-michael-wehar).
rus9384
<cc.complexity-theory><complexity-classes>
Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$
Alexey Milovanov
# Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

(Asked by: username_0 on 2017-09-01)

1) What classes contain $\textbf{PSPACE}$, are contained in $\textbf{EXP}$ and (presumably) are not equal to $\textbf{PSPACE}$ nor to $\textbf{EXP}$?

A possible class satisfying this requirement: the class of languages that can be recognized in exponential time and subexponential memory.

2) Which of these classes are provably strictly larger than $\textbf{P}$?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Similar to your example, you could consider the class of languages that can be decided by an alternating Turing machine that runs in subexponential time using polynomial space.  
> **username_1**: Because PSPACE = AP and APSPACE = EXP, you could alternatively think of this as trying to find a class between AP and APSPACE.  :)  
> **username_1**: Thinking about it a little differently, there might be some natural classes between PSPACE and APSPACE.  Adding a fixed number of alternations doesn't break out of PSPACE, but if you allow the number of alternations to be bounded by some function of n, then you will be between PSPACE and APSPACE.  
> **username_1**: I find these kinds of fundamental problems on time vs space to be very interesting.  If you would ever like to chat about this, please let me know.  Thank you again for posting this question!  
> **username_1**: Also, you could consider problems that are polynomial space verifiable with subexponential witness sizes.  
> **username_2**: @MichaelWehar, what that function would be? $\log^k n$?  
> **username_1**: @username_2 Hi there!  Not sure if I understand you question.  Could you possibly clarify your question further?  :)  
> **username_2**: @MichaelWehar, if you'll take $O(\log n)$ it still is in $\mathsf{PSPACE}$.  
> **username_1**: @username_2 I'm not quite sure what you are suggesting to be $O(\log(n))$.  
> **username_2**: @MichaelWehar, number of alternations. In fact, if number of alternations is $f(n)$ then the equivalent class is $DTISP(exp,2^{f(n)})$, for any $f(n)\in\Omega(\log n)$.  
> **username_1**: @username_2 So the classic result is that $DTIME(f(n))$ is a subset of $ASPACE(\log(f(n)))$.  I don't see how we can modify the proof to get that $DTISP(2^n, 2^{f(n)})$ is a subset of $\Sigma^{f(n)}SPACE(poly(n))$.  
> **username_1**: The point with the proof is that you have a large number of alternations, but each quantifier is "thin" in the sense that few bits are quantified over for each alternation.  We could "slightly" reduce the number of alternations by making the quantifiers less thin, but I don't see how to get your result.  If you have a proof, please do share as I'm very interested in this subject!  Again, it is possible that I missed something.  :)  
> **username_1**: @username_2 Hi again, just wanted to follow-up and see what you think about my response.  :)  
> **username_2**: @MichaelWehar, it is subset, proof is similar to proof $\mathsf{EXP=APSPACE}$. Harder part is to prove that opposite is true. You will need to reuse the space (that's why under assumption of $\mathsf{P = NP\ne PSPACE}$ TQBF with $f(n)$ quantifiers is not solvable in $2^{f(n)}$ time, only in $n^{f(n)}$ - time can't be reused).  
> **username_1**: @username_2 Thank you very much for the reply!!  But, I just don't see it.  In the $EXP$ subset $APSPACE$ proof, you use exponentially many alternations.  It doesn't seem trivial to generalize this as you suggested as each alternation corresponds with one step of the computation.  But, here we are not reducing the number of steps, rather we are reducing the space.  
> **username_1**: @username_2 Could you possible write up your proof??  :)  
> **username_2**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/65155/discussion-between-username_2-and-michael-wehar).  

---

## 3 answers

### Answer by username_3 on 2017-09-01. Score: 7

Depends what you mean by "class".

I don't know of any natural class that satisfies that, but certainly one can do the following:

Consider the set of languages that are decidable in time $2^n$ (exactly, not just any exponential). This is strictly contained in EXP by the time-hierarchy theorem.
Take the union of this set and PSPACE, and you have a class that strictly contains P (again, time hierarchy), contains PSPACE, and is contained in EXP (and presumably, if PSPACE$\neq$ EXP, then there is also strict containemnt here).


---

### Answer by username_4 on 2017-09-04. Score: 3

It is consistent with current state of knowledge that PSpace=ExpTime. Therefore there are no classes that we know that falls strictly between them.

If they are not equal there are infinite number of classes between them by diagonalization (Ladner's theorem).

If you are looking for well known classes that we know contain PSpace and are contained in ExpTime you can check complexity zoo. Based on [zoology](https://www.math.ucdavis.edu/~greg/zoology/diagram.xml) [RG](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#rg) is an example. Other than that there doesn't seem to be any class with name that falls between them.


---

### Answer by username_2 on 2017-09-04. Score: 2

I can show two ways (of course I don't claim that they are the only options):

1. Generalize [username_3](https://cstheory.stackexchange.com/users/7531/shaull)'s answer and take $\mathsf{PSPACE\cup DTIME}(2^{O(n^k)})$ for some fixed $k$.
2. But you may be interested in another variant. You can take $f(n)$ such that $f(n)\in O(2^{n^k})\cap\omega(poly(n))$ for some fixed $k$. Under assumption that $\mathsf{EXP\not\subset DSPACE}(f(n))$ you just take a complexity class $\mathsf{DTISP}(exp,f(n))$. The difference between this and $\mathsf{DSPACE}(f(n))\cap \mathsf{EXP}$ is that former requires the same algorithm to run in exponential time and $f(n)$ space. Latter only requires separate algorithms to do these things separately. It will contain $\mathsf{PSPACE}$ and be contained in $\mathsf{EXP}$. For example you can replace $(f(n))$ with $qpoly$ (quasipolynomial) and get $\mathsf{DTISP}(exp,qpoly)$.

P.S. They all are provably larger than $\mathsf P$. Because you are asking about a class that is strictly larger than $\mathsf{PSPACE}$ under assumption $\mathsf{PSPACE\ne EXP}$. Under the same assumption it will also strictly contain $\mathsf{P}$. Under opposite assumption of $\mathsf{PSPACE=EXP}$ we know that $\mathsf{P\ne PSPACE}$ (due to time hierarchy theorem) and since that class is at least as large as $\mathsf{PSPACE}$, it will strictly contain $\mathsf P$ as well.

Edit: missed that you already suggested that complexity class in question. So, replaced it.


---

