4 ms·
Oh thank you very much, this changed my understanding of NP and what the fuss is all about (I was thinking more of a TM which has access to randomness, as the n
by darkmighty 11y ago
Oh thank you very much, this changed my understanding of NP and what the fuss is all about (I was thinking more of a TM which has access to randomness, as the name suggests for me). I think need to read more about precisely what "multiple possible transitions from any given state" allows.
Btw, is there a class that is actually "Turing machines with randomness in polynomial time" and is it more powerful than "Turing machines in polynomial time"?
- teraflop 11y agoExcellent question! We call those "probabilistic Turing machines", and the most interesting complexity classes associated with them are ZPP and BPP. 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.
- darkmighty 11y agoAh 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 ?)