Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ?
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.
