39
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Oct 25, 2010 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Oct 25, 2010 at 22:49
  • 4
    $\begingroup$ @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? $\endgroup$
    – Joe Fitzsimons
    Commented Oct 26, 2010 at 2:20
  • 1
    $\begingroup$ @Joe, I haven't considered that idea; it might work. $\endgroup$
    – Peter Shor
    Commented Oct 26, 2010 at 3:38
  • 2
    $\begingroup$ Joe, maybe you should post it as an answer $\endgroup$
    – Suresh Venkat
    Commented Oct 26, 2010 at 17:50

4 Answers 4

Reset to default
28
$\begingroup$

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.)

Improve this answer
$\endgroup$
9
  • $\begingroup$ @Peter: Noam is right. I quote the following lines from here: ...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... $\endgroup$
    – Sadeq Dousti
    Commented Oct 27, 2010 at 5:03
  • $\begingroup$ In which case my answer is most likely nonsense. Thanks for pointing this out. $\endgroup$
    – Joe Fitzsimons
    Commented Oct 27, 2010 at 8:32
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Oct 27, 2010 at 8:48
  • 1
    $\begingroup$ I assume multiple provers are not known to help. Is this correct? $\endgroup$
    – Peter Shor
    Commented Oct 27, 2010 at 11:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Boaz Barak
    Commented Oct 29, 2010 at 4:59
25
$\begingroup$

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, 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 by Broadbent, Fitzsimons, and Kashefi showed that a closely-related statement is true.

Improve this answer
$\endgroup$
22
$\begingroup$

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 (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.

Improve this answer
$\endgroup$
11
$\begingroup$

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. 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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Boaz Barak
    Commented Oct 29, 2010 at 4:52
  • $\begingroup$ @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! $\endgroup$
    – Joe Fitzsimons
    Commented Oct 29, 2010 at 5:02

Your Answer

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

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