Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
ty very much indeed – LMG Nov 17 '12 at 9:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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