4
$\begingroup$

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}$?

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ Because PSPACE = AP and APSPACE = EXP, you could alternatively think of this as trying to find a class between AP and APSPACE. :) $\endgroup$
    – Michael Wehar
    Sep 1, 2017 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Sep 1, 2017 at 18:55
  • 1
    $\begingroup$ @MichaelWehar, what that function would be? $\log^k n$? $\endgroup$
    – rus9384
    Sep 4, 2017 at 18:50
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – rus9384
    Sep 5, 2017 at 3:13
  • 1
    $\begingroup$ @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). $\endgroup$
    – rus9384
    Sep 5, 2017 at 23:13

3 Answers 3

Reset to default
7
$\begingroup$

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).

Improve this answer
$\endgroup$
3
$\begingroup$

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 RG is an example. Other than that there doesn't seem to be any class with name that falls between them.

Improve this answer
$\endgroup$
2
$\begingroup$

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

  1. Generalize 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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