<p>Yes, the question of whether coNP has an interactive proof where the prover is weaker than #P (say, polytime with access to NP oracle) is a well known open question.
The following paper of <a href="https://www.cs.virginia.edu/%7Emohammad/files/papers/07%20SamNP.pdf" rel="nofollow noreferrer">Haitner, Mahmoody and Xiao</a> (A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP, CCC 2010) discusses this question and shows some consequences of the assumption that this cannot be done.</p>

CC BY-SA 4.0
2010-10-27T23:34:38.047Z
2022-10-17T06:30:05.840Z
2022-10-17T06:30:05.840Z
Boaz Barak
<p>This is a known (wonderful) open problem that I've worked on from time to time without success.</p>

<p>Avi Wigderson and I mentioned the problem in our <a href="http://www.scottaaronson.com/papers/alg.pdf">algebrization paper</a>, where we raised the question of whether or not containments such as coNP &sube; IP<sub>NP</sub> can be proved via algebrizing techniques. (Here IP<sub>NP</sub> denotes IP with a BPP verifier and a BPP<sup>NP</sup> prover.)  If (as I conjecture) the answer is no, then that would provide a formal reason why any interactive protocol like the one Peter asks for would require non-relativizing techniques that go "fundamentally beyond" the ones used for IP=PSPACE.</p>

<p>An analogous question is whether or not BQP = IP<sub>BQP</sub>, where IP<sub>BQP</sub> means IP with a BPP verifier and a BQP (quantum polynomial-time) prover.  That question is also open---although a <a href="http://arxiv.org/pdf/0807.4154">recent breakthrough</a> by Broadbent, Fitzsimons, and Kashefi showed that a closely-related statement is true.</p>

CC BY-SA 2.5
2010-10-27T21:18:17.007Z
2010-10-27T21:18:17.007Z
Scott Aaronson
<p>Since Suresh has suggested I post my comment as an answer, I will. However, I do not consider this to constitute a full answer as I have not attempted to prove this, and it may turn out to be a dead end.</p>

<p>The original IP=PSPACE proof works by producing an interactive proof for <a href="http://qwiki.stanford.edu/index.php/Complexity_Garden#qbf">QBF</a>. A restricted case of QBF, $\mbox{QBF}_k$ is complete for $\Sigma^P_k$. The same arithmetization strategy will work equally well for $\mbox{QBF}_k$. The computationally difficult part of the provers strategy would seem to be reducing the degree of the polynomials involved and evaluating the QBF formulae arising. It seems likely that this can be achieved using an oracle for the corresponding level of the polynomial hierarchy ($\Sigma^P_k$), by redoing the arithmitization in each round, once the verifier has provided their random choices.</p>

CC BY-SA 2.5
2010-10-29T04:52:40.447Z
the issue already arises in the proof for coNP. The sumcheck protocol has n rounds (one for each variable). In each round, the prover needs to come up with the coefficients of the polynomial that is obtained by some exponentially large sum. I don't know how to do it using less power than #P.
Boaz Barak
CC BY-SA 2.5
2010-10-29T05:02:49.077Z
@Boaz: Yes, I think this approach is destined to fail. I thought I had seen a version of the arithmetization done somewhere in such a way that the polynomial only took on values 1 or 0 for inputs of 0s and 1s. If this is the case, it seems like you could use an oracle for a corresponding decision problem. Then again, I may just have imagined that!
Joe Fitzsimons
CC BY-SA 2.5
2010-10-27T00:57:22.980Z
2010-10-27T00:57:22.980Z
Joe Fitzsimons
<p>Even for giving an IP for coNP, using current techniques, one needs to arithmetize, i.e. use counting, which means essentially the full power of #P.  Any weaker prover even for coNP would be very interesting, I think (in particular would imply a new non relativing technique.)</p>

CC BY-SA 2.5
2010-10-27T05:03:00.100Z
@Peter: Noam is right. I quote the following lines from [here](http://www.cs.cornell.edu/courses/cs7890/2010sp/MohammedMahmoody3110.htm): ...basing collision resistant hashing on the worst-case hardness of NP through a black-box reduction implies an interactive proof system for co-NP with the prover in BPP^NP...All known (even multi-prover) proof systems for co-NP require provers with #P complexity...
Sadeq Dousti
CC BY-SA 2.5
2010-10-27T08:32:41.253Z
In which case my answer is most likely nonsense. Thanks for pointing this out.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-27T08:48:29.027Z
Actually, this is really interesting, given that an interactive proof for Graph non-Isomorphism only needs a prover with an oracle for that problem. It feels like evidence that either GI is very very weak (like in P) or the bounds for interactive proofs of levels of the polynomial hierarchy are likely very loose.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-27T11:21:04.110Z
I assume multiple provers are not known to help. Is this correct?
Peter Shor 
CC BY-SA 2.5
2010-10-27T13:13:58.177Z
indeed AFAIK, multiple provers are not known to help.
Noam
CC BY-SA 2.5
2010-10-29T04:59:02.943Z
@Joe The proof for graph non isomorphism is a constant round public coin proof, thus putting it in the class AM (widely believed to equal NP, and hence GI and GNI are believed to be in $NP \cap coNP$). This is much lower than polynomial round proof that is believed to be necessary for proving membership in coNP complete problems.
Boaz Barak
CC BY-SA 2.5
2010-10-29T05:07:12.260Z
@Boaz: Yes, I realise that GI and GNI are likely much weaker than NP. I just find it strange that for a reasonable group of problems all you need is an oracle for that problem, where as this does not seem to be true for levels of the polynomial hierarchy.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-05T15:35:53.950Z
Could you put it in P$^{\mathrm{parity-P}}$ by using polynomials over the field GF($2^k$)?
Peter Shor 
CC BY-SA 2.5
2010-11-12T19:32:18.130Z
I think so, but am not sure (need to verify that exponential-size arithmetic in GF(2^k) can indeed be done using parity-P oracle)
Noam
CC BY-SA 2.5
2010-10-27T04:50:08.870Z
2010-10-27T04:50:08.870Z
Noam
<p>We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want to give an interactive proof of membership in a $\Sigma_2$ language. Is it enough to be able to solve problems in $\Sigma_2$? Is solving problems in $\Sigma_5$ adequate? More generally, if you can solve $\Sigma_k$ or $\Pi_k$ problems, for what $\Sigma_\ell$ is this sufficient to generate interactive proofs of all languates in $\Sigma_\ell$?</p>

<p>This question was inspired by <a href="https://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers">this cstheory stackexchange question</a>.</p>

CC BY-SA 3.0
2017-11-28T22:48:09.137Z
why sigma5? what are the predicates?
Steve Uurtamo
CC BY-SA 2.5
2010-10-25T18:47:49.303Z
Are you only interested in the single prover case or are you interested in the case of multiple provers? It seems to me that the obvious way to attack this would be via PCPs, which might be straight forward for two provers,but probably won't work for a single prover.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-25T22:49:08.017Z
I'd be interested in both cases. I've wondered about this question for single provers for quite a while, but hadn't thought at all about multiple provers.
Peter Shor 
CC BY-SA 2.5
2010-10-26T02:20:16.043Z
@Peter: Looking over the IP=PSPACE paper, it seems that the proof would go through using $\mbox{QBF}_k$ (which is complete for $\Sigma^P_k$) rather than QBF, provided that you have a prover sufficiently powerful to calculate the polynomial identities arising from the arithmitization of the $\mbox{QBF}_k$. Am I missing something?
Joe Fitzsimons
CC BY-SA 2.5
2010-10-26T03:38:02.990Z
@Joe, I haven't considered that idea; it might work.
Peter Shor 
CC BY-SA 2.5
2010-10-26T17:50:34.620Z
Joe, maybe you should post it as an answer
Suresh Venkat
CC BY-SA 2.5
2010-10-26T21:16:14.757Z
@Suresh: I'm not sure it constitutes an answer. I haven't worked through it all.
Joe Fitzsimons
<cc.complexity-theory><interactive-proofs>
Interactive proofs for levels of the polynomial hierarchy
Peter Shor 
# Interactive proofs for levels of the polynomial hierarchy

(Asked by: username_0 on 2010-10-25)

We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want to give an interactive proof of membership in a $\Sigma\_2$ language. Is it enough to be able to solve problems in $\Sigma\_2$? Is solving problems in $\Sigma\_5$ adequate? More generally, if you can solve $\Sigma\_k$ or $\Pi\_k$ problems, for what $\Sigma\_\ell$ is this sufficient to generate interactive proofs of all languates in $\Sigma\_\ell$?

This question was inspired by [this cstheory stackexchange question](https://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers).

**Tags:** cc.complexity-theory, interactive-proofs
> **Comments:**
> **username_2**: Are you only interested in the single prover case or are you interested in the case of multiple provers? It seems to me that the obvious way to attack this would be via PCPs, which might be straight forward for two provers,but probably won't work for a single prover.  
> **username_0**: I'd be interested in both cases. I've wondered about this question for single provers for quite a while, but hadn't thought at all about multiple provers.  
> **username_2**: @Peter: Looking over the IP=PSPACE paper, it seems that the proof would go through using $\mbox{QBF}_k$ (which is complete for $\Sigma^P_k$) rather than QBF, provided that you have a prover sufficiently powerful to calculate the polynomial identities arising from the arithmitization of the $\mbox{QBF}_k$. Am I missing something?  
> **username_0**: @Joe, I haven't considered that idea; it might work.  
> **username_3**: Joe, maybe you should post it as an answer  
> **username_2**: @Suresh: I'm not sure it constitutes an answer. I haven't worked through it all.  
> **username_1**: why sigma5? what are the predicates?  

---

## 4 answers

### Answer by username_6 on 2010-10-27. Score: 28 | Accepted answer

Even for giving an IP for coNP, using current techniques, one needs to arithmetize, i.e. use counting, which means essentially the full power of #P. Any weaker prover even for coNP would be very interesting, I think (in particular would imply a new non relativing technique.)

> **Comments:**
> **username_7**: @Peter: Noam is right. I quote the following lines from [here](http://www.cs.cornell.edu/courses/cs7890/2010sp/MohammedMahmoody3110.htm): ...basing collision resistant hashing on the worst-case hardness of NP through a black-box reduction implies an interactive proof system for co-NP with the prover in BPP^NP...All known (even multi-prover) proof systems for co-NP require provers with #P complexity...  
> **username_2**: In which case my answer is most likely nonsense. Thanks for pointing this out.  
> **username_2**: Actually, this is really interesting, given that an interactive proof for Graph non-Isomorphism only needs a prover with an oracle for that problem. It feels like evidence that either GI is very very weak (like in P) or the bounds for interactive proofs of levels of the polynomial hierarchy are likely very loose.  
> **username_0**: I assume multiple provers are not known to help. Is this correct?  
> **username_6**: indeed AFAIK, multiple provers are not known to help.  
> **username_4**: @Joe The proof for graph non isomorphism is a constant round public coin proof, thus putting it in the class AM (widely believed to equal NP, and hence GI and GNI are believed to be in $NP \cap coNP$). This is much lower than polynomial round proof that is believed to be necessary for proving membership in coNP complete problems.  
> **username_2**: @Boaz: Yes, I realise that GI and GNI are likely much weaker than NP. I just find it strange that for a reasonable group of problems all you need is an oracle for that problem, where as this does not seem to be true for levels of the polynomial hierarchy.  
> **username_0**: Could you put it in P$^{\mathrm{parity-P}}$ by using polynomials over the field GF($2^k$)?  
> **username_6**: I think so, but am not sure (need to verify that exponential-size arithmetic in GF(2^k) can indeed be done using parity-P oracle)  

---

### Answer by username_5 on 2010-10-27. Score: 26

This is a known (wonderful) open problem that I've worked on from time to time without success.

Avi Wigderson and I mentioned the problem in our [algebrization paper](http://www.scottaaronson.com/papers/alg.pdf), where we raised the question of whether or not containments such as coNP ⊆ IPNP can be proved via algebrizing techniques. (Here IPNP denotes IP with a BPP verifier and a BPPNP prover.) If (as I conjecture) the answer is no, then that would provide a formal reason why any interactive protocol like the one Peter asks for would require non-relativizing techniques that go "fundamentally beyond" the ones used for IP=PSPACE.

An analogous question is whether or not BQP = IPBQP, where IPBQP means IP with a BPP verifier and a BQP (quantum polynomial-time) prover. That question is also open---although a [recent breakthrough](http://arxiv.org/pdf/0807.4154) by Broadbent, Fitzsimons, and Kashefi showed that a closely-related statement is true.


---

### Answer by username_4 on 2010-10-27. Score: 22

Yes, the question of whether coNP has an interactive proof where the prover is weaker than #P (say, polytime with access to NP oracle) is a well known open question.
The following paper of [Haitner, Mahmoody and Xiao](https://www.cs.virginia.edu/%7Emohammad/files/papers/07%20SamNP.pdf) (A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP, CCC 2010) discusses this question and shows some consequences of the assumption that this cannot be done.


---

### Answer by username_2 on 2010-10-27. Score: 11

Since Suresh has suggested I post my comment as an answer, I will. However, I do not consider this to constitute a full answer as I have not attempted to prove this, and it may turn out to be a dead end.

The original IP=PSPACE proof works by producing an interactive proof for [QBF](http://qwiki.stanford.edu/index.php/Complexity_Garden#qbf). A restricted case of QBF, $\mbox{QBF}\_k$ is complete for $\Sigma^P\_k$. The same arithmetization strategy will work equally well for $\mbox{QBF}\_k$. The computationally difficult part of the provers strategy would seem to be reducing the degree of the polynomials involved and evaluating the QBF formulae arising. It seems likely that this can be achieved using an oracle for the corresponding level of the polynomial hierarchy ($\Sigma^P\_k$), by redoing the arithmitization in each round, once the verifier has provided their random choices.

> **Comments:**
> **username_4**: the issue already arises in the proof for coNP. The sumcheck protocol has n rounds (one for each variable). In each round, the prover needs to come up with the coefficients of the polynomial that is obtained by some exponentially large sum. I don't know how to do it using less power than #P.  
> **username_2**: @Boaz: Yes, I think this approach is destined to fail. I thought I had seen a version of the arithmetization done somewhere in such a way that the polynomial only took on values 1 or 0 for inputs of 0s and 1s. If this is the case, it seems like you could use an oracle for a corresponding decision problem. Then again, I may just have imagined that!  

---

