19
$\begingroup$

It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such interactive proofs when the provers are restricted in power? E.g., what is the class of languages that admit two-prover interactive proofs with polynomial-time provers?

More precisely, let's say that on an input x I allow the provers arbitrary pre-computation time, but once the interaction with the verifier starts they are restricted to using polynomial space (including storing the results of any pre-computation), and polynomial time to compute their answers to the verifier's question. Let's also assume that these space and time bounds are a fixed polynomial in the length of the questions that will be sent by the verifier (instead of the length of x), in order to preclude a more trivial solution in which the verifier would somehow exhaust the prover's space bound by asking polynomially more questions.

Clearly, this is enough for NP. What about PSPACE? If there was only the space bound they could do it, but what with the time bound? Are there any interesting results in that direction?

I am also interested in other limitations that one might consider on the provers. One of those would be the amount of communication prover->verifier, which I think has been thoroughly studied in the context of PCPs. What are the other interesting constraints?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
17
$\begingroup$

It sounds like this class would be exactly MA. The witness could be the results of pre-processing (which is of polynomial size). The probabilistic verification procedure would then be to simulate the protocol, including the multiple provers (who are polynomial-time given the results of pre-processing).

Russell Impagliazzo

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good point, thanks. More generally I was wondering in what ways multiple provers could prove languages which are outside of their time bound T (modulo the pre-processing step), to a poly-time verifier, and your answer shows that this will never be more than the corresponding MA(T), with a T-time verifier. But how does it compare to some poly-time verifier class? Say if the provers now are allowed to be PSPACE, they can still prove NEXP. Can they be any more restricted and still prove the same thing? $\endgroup$
    – Thomas
    Commented Aug 28, 2010 at 2:59
2
$\begingroup$

If the two provers are restricted to be two BQP machines that do not communicate with each other, but share entanglement, while the verifier is in BPP, then the two provers can proof any language in BQP to the classical verifier using the Universal Blind Quantum Computation protocol of Broadbent, Fitzsimons, and Kashefi. This protocol has also been used by the same authors as a building block to show QMIP=MIP*.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thanks Martin, I didn't want to mention my own work. $\endgroup$
    – Joe Fitzsimons
    Commented Aug 30, 2010 at 3:30

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.