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.

$\endgroup$
0

1 Answer 1

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.

$\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$ Commented 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$ Commented Nov 22, 2018 at 21:00

Your Answer

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

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