HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Symmetry of IP complexity class

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
symmetryclasscomplexity

Problem

Wikipedia defines the IP complexity class as follows:


A language $L$ belongs to IP if there exists $V,P$ such that for all
$Q$, $w$,
$$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

Note that this definition is asymmetric; it says (if we are polynomial-bound) we can be convinced $w\in L$, but says nothing about convincing us that $w\notin L$. We could define a class coIP containing the complements of languages in IP; that is


A language $L$ belongs to coIP if there exists $V,P$ such that for all
$Q$, $w$,
$$w\notin L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\in L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

It turns out IP=PSPACE and clearly PSPACE is symmetric under taking complement. Thus IP=coIP. Is there a direct way to see this? That is,


Given a proof system $(V,P)$ for proving membership in $L$, can we use
it to construct a proof system $(V',P')$ for proving membership in
$\bar L$?

Solution

There is no relativizing technique to show that $\mathrm{IP}$ is closed under complement.

Clearly, $\mathrm{NP}\subseteq\mathrm{IP}$.

Fortnow and Sipser gave an oracle relative to which $\mathrm{co}$-$\mathrm{NP}$ does not have interactive proof system.

So, you have to study the arithmetization technique that settles down this conjecture (long ago).

Are there interactive protocols for CO-NP

Context

StackExchange Computer Science Q#91748, answer score: 2

Revisions (0)

No revisions yet.