By the definition, in an Interactive Proof system the verifier is allowed to generate random numbers, which allows the omniscient prover to not fool it in the vast majority of cases for every problem in $\mathsf{PSPACE}$. The verifier is a polynomial time machine, therefore an ability to generate random numbers makes it a member of $\mathsf{RP}$ solvers.

However, it is widely believed that $\mathsf{P=RP=BPP}$. If that's true would it also be possible to derandomize the verifier in Interactive Proof systems without the system losing its power at more than a polynomial factor?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.