1
$\begingroup$

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?

$\endgroup$

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.