3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Questions about the lower end of the hierarchy will still be open. For example, what are the relations between L, NL, and P? On the higher end, what are the relations between P, PSPACE, and EXP? $\endgroup$ Jun 9, 2018 at 21:14

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

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.