Re:An Argument for P=NP (2005) [pdf]
by darkmighty on Monday August 17, 2015 @08:09PM
(#10076909)
Ah that's interesting, ill read more on those. But did we just come back full circle and the existence of strong pseudorandom generators depends on P!=NP? :P
( P!=NP => BPP=P => P=BPP!=NP ?)
ZPP contains problems for which the answer is guaranteed to be correct, and the machine halts in expected polynomial time -- the so-called "Las Vegas" algorithms. And then there's BPP, containing algorithms which always run in polynomial time but whose outputs have a constant, bounded probability of being wrong -- the "Monte Carlo" algorithms.
Currently, we know that P ⊆ ZPP ⊆ BPP, but we haven't yet proved whether or not any of those classes are equal to each other. However, there's apparently mounting evidence -- most of which goes over my head -- that in fact P=BPP; in other words, any randomized algorithm can be "derandomized" with the use of a sufficiently strong pseudorandom number generator.