Randomized Computation
While the worst-case complexity of a problem is important, it is sometimes sufficient to consider algorithms which solve a problem correctly, and efficiently on “most” (but not all) inputs. Algorithms that are not deterministic but make randomized choices, and are correct and efficient with high probability — but not with certainty — are sometimes useful too.
With that noted, randomized computation (also called probabilistic computation) will now be considered.
In order to make this formal, yet another variant of a Turing machine — a probabilistic Turing machine — will be introduced. This will be used to define a variety of complexity classes involving algorithms that decide membership in languages, using at most polynomial time — but which are “randomized” and can fail in a variety of ways.
Technical results explaining why it is generally believed that these complexity classes do not include NP-complete languages will also be described.
Lecture #24: Probabilistic Computation — Part One
Why This is Included
If the complexity of probabilistic computation is to be studied then a model of computation, that supports this, must be introduced, so that algorithms can be presented and the cost to execute them can be defined. Complexity classes that correspond to this new notion of computation are also needed.
This lecture introduces a model of computation that can be used, along with complexity classes that that can be used to consider computations with one-sided error, or with no error at all (but whose running times might depend on random choices that are being made).
Preparatory Reading
- Probabilistic Computation — Part One:
[ PDF ]
[ Video ]
- Supplement: Proof of Lemma #2 [ PDF ]
Lecture Presentation
Finishing Up
Lecture #25: Probabilistic Computation — Part Two
Why This is Included
The previous lecture concerned randomized algorithms, for decision problems, with either error at all (except that computations could signal failure) or error on only one side. Algorithms with two-sided error — so that they can accept some inputs that should be rejected, and they can also reject some inputs that should be rejected — are also of interest, provided that the probability of error is acceptably small.
Unfortunately, the algorithms that have been introduced, and their analysis, depend on an unrealistic assumption: They assume that “perfect” sources of sequences of random bits are used, when “imperfect” sources of sequences of random bits are more likely to be available instead.
This lecture introduces a complexity class including languages that can be decided with randomized algorithms with two-sided error — and it considers whether the randomized complexity classes, now introduced, would change if they were defined using imperfect sources or random bits instead of perfect random sources.
Preparatory Reading
- Probabilistic Computation — Part Two:
[ PDF ]
[ Video ]
- Supplement: Proofs of Claims — Error Reduction [ PDF ]
Lecture Presentation
Finishing Up
Lecture #26: Probabilistic Computation — Part Three
Why This is Included
At this point, complexity classes for randomized computation have been introduced. However, there are several questions that one might expect to be answered, early on in a study of this, that we have not addressed:
-
Are there computational problems that have efficient randomized algorithms, when no efficient deterministic algorithms for these problems are not known too? In particular, are there any languages that are known to be in BPP that are not also known to be in P?
-
Are the complexity classes RPP, ZPP and BPP closed under polynomial-time many-one reductions? Which, if any, of the languages in these complexity classes are known to be complete for these complexity classes, with respect to these reductions?
-
How are RP, ZPP and BPP related to other complexity classes that we have studied — including classes in the Polynomial Hierarchy and P/Poly? What, if anything, is known — or conjectured — about the relationship between BPP and P?
Answering these questions is more challenging than one might expect! Nevertheless, they are reasonable questions to ask, and they have motivated a considerable amount of research. This lecture describes some of what is presently known about this.
