Questions tagged [interactive-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9
votes
1answer
227 views

closure properties of IP(2pfa) and AM(2pfa)

IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic ...
17
votes
2answers
599 views

MIP with efficient provers

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