I'm now studying Interactive Proof System in Goldreich's textbook and here. I have the following question:

Suppose P=BPP, then this show that randomness doesn't give us power over deterministic model (moreover, this would show that we can derandomize every randomness algorithm into deterministic model). Now, In interactive proof system, we know that if Verifier is deterministic, then Prover can guess all questions that Verifier would ask. So, interactive proof system is useless without randomness. Moreover, interactive proof system such that Verifier is not using randomness would be equivalent to class NP. Now, does this mean if P=BPP, then IP=NP? Why I say something like that? Well, since Prover has unbounded computation power, then Prover can simulate randomness by derandomness.

Thank you!


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.