5
$\begingroup$

I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest class, but how much it is big?

May i say that ${\sf PSPACE}$ is a subset of ${\sf IP}$? or that they may intersect?

Can you give me a easy clarification about it?

$\endgroup$

1 Answer 1

9
$\begingroup$

IP = PSPACE is a famous result (and indeed paper) by Adi Shamir in 1992.

Furthermore, we clearly have NP $\subseteq$ PSPACE and coNP $\subseteq$ PSPACE, but we don't know how NP relates to coNP. There are several reasons to believe that determining the relationship between NP and coNP is difficult, some of which are discussed in this recent thread.

$\endgroup$
1
  • $\begingroup$ ty very much indeed $\endgroup$
    – LMG
    Commented Nov 17, 2012 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.