0
$\begingroup$

If its proven today that $P=PSPACE$ the whole polynomial hierarchy collapses. Moreover since $BQP \subseteq PSPACE$, it will also result in $P=BQP$.

However unlikely the above scenario is, hypothetically if this were the case what are the complexity classes (the most important ones) that will survive this collapse into $P$. The classes we are talking about:

  1. Should be above $P$ (thus $L, NC, NL$ etc. could be temporarily ignored)
  2. Are interesting and open enough to be studied (thus $E, EE, ALL$ etc. can be ignored)

We are concerned about both the traditional as well as Quantum Complexity classes.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The time hierarchy theorem still tells us that $$\mathrm{P}\subsetneq \mathrm{EXP}\subsetneq\mathrm{2\text{-}EXP} \subsetneq \dots\,,$$ and likewise for the analogous space classes and nondeterministic time and space classes.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. I am aware of this thus I mentioned that we ignore the classes like E (exponential), EE (Doubly Exponential) etc. in (2.) We are interested in the classes that will still be (vaguely speaking) 'open' (for example that might have the potential to collapse into some lower class similar to P vs. PSPACE).. $\endgroup$
    – TheoryQuest1
    Nov 22, 2018 at 20:24
  • $\begingroup$ Ah. I've never heard these classes referred to by the names you listed, so I simply didn't recognize them. $\endgroup$
    – David Richerby
    Nov 22, 2018 at 21:00

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.