0
$\begingroup$

Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE

$\endgroup$
0

1 Answer 1

4
$\begingroup$

If P = PSPACE then since $\text{P} \subseteq \text{coNP} \subseteq \text{PSPACE}$, we can conclude that coNP=PSPACE, and by contrapositive this means that if $\text{coNP} \neq \text{PSPACE}$ then $\text{P} \neq \text{PSPACE}$. Since the question of P vs PSPACE is unsolved, one can conclude that there's no known proof of $\text{coNP} \neq \text{PSPACE}$.

$\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.