2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Answer any more complexity theory questions and you'll have to change your name to P/NP Nick. ;-) $\endgroup$ Commented Jun 8, 2018 at 13:50

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.