patternMinor
Impact of Polynomial Time Algorithm for an NP Complete problem on Complexity Theory
Viewed 0 times
problemimpactpolynomialtheorytimealgorithmcompleteforcomplexity
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#92909, answer score: 3
Revisions (0)
No revisions yet.