Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of an unbounded power. It is known to be equal to $\mathsf{PSPACE}$.

Making the verifier a deterministic machine would make a complexity class $\mathsf{dIP}$ which is known to be equal to $\mathsf{NP}$.

However, if $\mathsf{P=BPP}$ would that mean that a deterministic verifier is as powerful as a probabilistic verifier, resulting in some implications believed to be false by the majority of computer scientists?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.