patternMinor
Relation between interactive proof systems (IP), NP, coNP, PSPACE
Viewed 0 times
conpinteractivesystemspspacebetweenrelationproof
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#6679, answer score: 9
Revisions (0)
No revisions yet.