Under the assumption that a PSPACE-hard problem A can be solved in polynomial time, is the following argumentation valid?

Since every problem in PSPACE can be reduced to A in polynomial time, every problem in NP which is a subset of PSPACE is included. That means that each Problem in NP is solvable in polynomial time and therefore P = NP.

Since coNP is a subset of PSPACE as well, we can argue that every problem in coNP can be reduced to A and therefore be solved in polynomial time as well, which means that P = coNP.

Therefore we can say that P = NP = coNP.

I don't see a problem with this argumentation at the moment, but it seems a bit too simplistic to me, so is this a valid way of arguing for the equality above?

up vote 3 down vote accepted

Your argument is perfectly fine. However, you actually do not even have to argue with polynomial reduction. Since $\textsf{P} \subseteq \textsf{NP}, \textsf{coNP} \subseteq \textsf{PSPACE}$, under the assummption that there is a $\textsf{PSPACE}$-hard problem solvable in polynomial time (i.e. it is in $\mathsf{P}$), you also have $\textsf{PSPACE} \subseteq \mathsf{P}$. Now $\textsf{NP}, \textsf{coNP}, \textsf{PSPACE}$ are sandwiched in $\mathsf{P}$ and thus, equality holds for the $\subseteq$ relations above.

  • 2
    Answer any more complexity theory questions and you'll have to change your name to P/NP Nick. ;-) – David Richerby Jun 8 at 13:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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