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.

  • $\begingroup$ anyone please ? $\endgroup$ – TheoryQuest1 Nov 23 '18 at 11:38

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.

  • $\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 '18 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 '18 at 21:00

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.