Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine with a psuedo-random number generator can't do? (a trivial thing it can do would be generating truly random numbers)
2
-
1$\begingroup$ Reading "practical difference" and "Turing machine" in one sentence is weird. $\endgroup$– Raphael ♦Mar 17, 2014 at 21:49
-
$\begingroup$ believe this is a major open problem subject to ongoing research expressed as eg BPP=?P class separations etc... $\endgroup$– vznMar 18, 2014 at 3:51
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
As long as decision problems (or optimization problems) are concerned, probabilistic Turing machines are equivalent to non-probabilistic Turing machines, since you can just simulate all the possible coin tosses (there are some subtleties here since the probabilistic Turing machine could halt only with probability 1, but let's ignore them).
However, there could be a difference in efficiency. Using truly random coin tosses could allow you to solve a specific problem faster. However, it is conjectured that truly random coin tosses can't bring down the level of difficulty from non-polynomial to polynomial, that is, if you have a probabilistic polynomial time algorithm for a problem, then there exists a deterministic polynomial time algorithm for the problem. This conjecture is known as the P=BPP conjecture. The idea is that you can simulate the truly random coin tosses with a sufficiently sophisticated PRNG. The simulation might be costly in running time, but it incurs only a polynomial overhead, and from this point of view that's a cost we're willing to pay.
Practically speaking, PRNGs are good enough, although in some rare cases you need to be slightly careful and use something beyond the fastest known PRNG. Only in cryptography does it sometimes make sense to use truly random coin tosses, since you can get absolute security guarantees this way (one-time pads), though in practice cryptographic PRNGs are used and they seem secure enough.
answered Mar 17, 2014 at 20:49
-
2$\begingroup$ This doesn't seem right: a deterministic TM cannot emulate a probabilistic one exactly, only up to probability 1. For example, a DTM cannot generate a true one-time pad that is resistant to unbounded-power cryptanalysis. Or is that what you meant to cover with the “subtleties” and the “rare cases”? $\endgroup$ Mar 17, 2014 at 20:57
-
$\begingroup$ I was referring only to decision problems (or optimization problems), of which generation of a one-time pad is not an example. An illustration of the subtlety is an algorithm which continuously tosses a coin until it turns head. This terminates with probability 1, but the number of coin tosses isn't bounded. $\endgroup$ Mar 18, 2014 at 0:44