[next] [prev] [prev-tail] [tail] [up]
So far, in analyzing programs for their time requirements, we have considered worst cases.
Programs whose worst cases are good, are obviously the most desirable ones for solving
given problems. However, in many circumstances we might also be satisfied with
programs that generally behave well for each input, where no better program available. In
fact, one might be satisfied with such programs, even when they contain a small
probability of providing wrong answers. Programs of this nature are created by allowing
instructions to make random choices. These types of programs are referred to as
probabilistic.
The first section of this chapter introduces probabilistic instructions into programs.
And the second section considers the usefulness of such programs that might err. The third
section introduces the notion of probabilistic Turing transducers for modeling the
computations of probabilistic programs. The chapter concludes with a consideration of
some probabilistic polynomial time classes of problems.
6.1 Error-Free Probabilistic Programs
6.2 Probabilistic Programs That Might Err
6.3 Probabilistic Turing Transducers
6.4 Probabilistic Polynomial Time
Exercises
Bibliographic Notes
[next] [prev] [prev-tail] [front] [up]