Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Assuming (hypothetically) someone proves $P=NP$ by providing a polynomial time algorithm for a $NP-Complete$ problem the Polynomial Hierarchy collapses.
What are the other (important) questions that are still left in complexity theory in respect to the remaining complexity classes?
If possible can someone help with a link where it might have been answered already (which I am guessing it might be) is perfectly fine too.
If P=NP, then it follows that P=co-NP, and NP=NP-complete (i.e. there are no NP-intermediate problems, which are in NP but not NP-complete).
But there are plenty of other divisions in the hierarchy which might still hold, and might not. P=NP wouldn't necessarily tell us anything about this.
On the higher end of things, how does NP relate to PSPACE? It's entirely possible that they're the same (only if P=NP: if P≠NP, they're definitely different), in which case all the classes in the middle (such as PP, which uses a probabilistic Turing machine) are collapsed together too.
On the lower end, how does P relate to L (logarithmic space)? There are various classes between these ones too, such as NL (nondeterministic log space), and these might all be collapsed into a single class also.
