Class Description

compIP: Competitive IP Proof System

Same as compNP but for interactive (IP) proofs instead of NP proofs.

More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in compIP [BG94].

Linked From

frIP: Function-Restricted IP Proof Systems

The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,

1. If the answer is "yes" then D^L(x) (D with oracle for L) accepts with probability at least 2/3.
2. If the answer is "no" then D^A(x) accepts with probability at most 1/3 for all oracles A.

Contains compIP [BG94] and Check [BK89].

Contained in MIP = NEXP [FRS88].

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in frIP [BG94].

More about...