1- what are the Consequences of ZPP=P ?

2- I know that if the advice from Adleman's theorem could be found in polynomial time then BPP=P , and this is likely to happen (I think that there is other evidence that P=BPP). what about evidence that P=ZPP without this result ? is there any other evidences ?


1 Answer 1


Under believable hardness assumptions, it is possible to construct pseudo-random generators that are strong enough to deduce all of the assertions P=BPP, P=RP, P=co-RP (and thus, P=ZPP). You can find the details in

Madhu Sudan, Luca Trevisan, Salil Vadhan. Pseudorandom generators without the XOR Lemma.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.