1
$\begingroup$

I am wondering if it is known whether probabilistic Turing machines are more powerful than deterministic ones, in the sense that they can solve problems faster on average, or can solve problems that deterministic Turing machines cannot? That is, if a Turing machine can "flip coins", does this allow it to do things it could not have done before?

I ask because in fields like cryptography, you always assume the adversary is a probabilistic Turing machine (that is they can draw from a random source), so I am guessing that this assumption means it is known that probabilistic Turing machines are stronger? Or is this just conjecture, but we use probabilistic Turing machines anyway because deterministic Turing machines are just a special case?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is a famous open problem in computer science theory. In particular, it comes down to whether BPP = P. It is widely conjectured and suspected that BPP = P, or in other words that randomness does not significantly increase the power of computer algorithms. However, we have no proof of this conjecture. So, it remains possible that randomness allows some problems to be solved more efficiently (our best guess is, this is probably not the case, but we cannot completely rule it out).

In cryptography, there are several reasons we tend to use probabilistic algorithms rather than deterministic algorithms (e.g., probabilistic Turing machines rather than deterministic Turing machines):

  1. Much of cryptography needs randomness to do anything. For instance, many techniques need to generate a random key, or generate a random value (nonce, IV, seed, salt, key, etc.). So, we need a probabilistic algorithm, so it has the ability to generate a random value, just to implement the cryptographic algorithm in the first place.

  2. Empirically, in practice, it is easy to generate random numbers on real computers. So we might as well pick a theoretical formulation that matches the capabilities that real computers have.

  3. In cryptography, we want to give the adversary every reasonable advantage. If we can prove security against all probabilistic polynomial-time algorithms, that is a more meaningful result than proving security against all deterministic polynomial-time algorithms (the former implies security against both, whereas the latter does not necessarily guarantee security against probabilistic algorithms). So, our definitions typically allow the adversary/attacker to use a probabilistic algorithm or probabilistic Turing machine, because this gives us a stronger, more meaningful notion of security.

$\endgroup$
3
  • $\begingroup$ Just to be sure, you write "or in other words that randomness does significantly increase the power of computer algorithms". Do you mean does not significantly...? (since if BPP-P then problems solved by probabililistic TM can also be solved by deterministic TM in poly time) $\endgroup$
    – user918212
    Commented Jun 24, 2022 at 18:34
  • $\begingroup$ @Generic, oops! Sorry, I meant "does not". I've edited my answer accordingly. Thank you for pointing that out, and I'm sorry for my error. $\endgroup$
    – D.W.
    Commented Jun 24, 2022 at 18:41
  • $\begingroup$ Thanks for the helpful answer! $\endgroup$
    – user918212
    Commented Jun 24, 2022 at 19:13

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.