[prev] [prev-tail] [tail] [up]

Bibliographic Notes

Probabilistic choices have been used for a long time in algorithms. The surge of interest in probabilistic computations is motivated by the work of Rabin (1976), Solovay and Strassen (1977), and Gill (1977).

The probabilistic algorithm in Example 6.1.1, for finding the kth smallest integer, is after Aho , Hopcroft , and Ullman (1974). The probabilistic algorithm in Example 6.2.1 for checking nonprimality is due to Rabin (1976). A similar algorithm was discovered independently by Solovay and Strassen (1977). Example 6.2.2 and Exercise 6.2.2 are from Freivalds (1979). Exercise 6.2.3 is from Schwartz (1980).

Probabilistic Turing machines were introduced by DeLeeuw , Moore , Shannon , and Shapiro (1956). Example 6.3.2 and Exercise 6.3.3 are from Freivalds (1979). Exercise 6.3.4, the results in Section 6.4, and Exercise 6.4.1, are due to Gill (1977).

Johnson (1984), Maffioli , Speranza , and Vercellis (1985) and Welsh (1983) provide surveys and bibliographies for the field.

[prev] [prev-tail] [front] [up]