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

 Bibliographic Notes

The applicability of parallel programs in general, and to the problem of finding the minimum element in a set in particular (see Example 7.1.1), is considered in Batcher (1968). The trade off between the size and depth complexities of parallel programs is considered in Valiant (1975). Applications of parallel programs to the design of sequential programs are exhibited in Megiddo (1981). Exercise 7.1.1(b) is from Muller and Preparata (1975).

Fortune and Wyllie (1978) introduced the CREW PRAM's, Ku cera (1982) introduced the COMMON PRAM's, and Goldschlager (1982) introduced the PRIORITY PRAM's. Shiloach and Vishkin (1981) adapted the trade-off results of Valiant (1975) for COMMON PRAM's. Exercise 7.2.3 and Exercise 7.2.5 are from Grolmusz and Ragde (1987). Exercise 7.2.4 is from Ku cera (1982).

Complexity of circuits were studied since Shannon (1949). Uniform families of circuits were introduced in Borodin (1977). Ruzzo (1981) and Allender (1986) discuss some variations of uniform families of circuits. Exercise 7.4.3 is from Ruzzo (1981). The class FNC was introduced in Pippenger (1979).

The results in Section 7.5 and in Exercise 7.5.5, relating uniform families of circuits with sequential computations, are from Borodin (1977). Exercise 7.5.5 is from Kannan (1982), and Exercise 7.5.6 is from Adleman (1978). Chandra , Stockmeyer , and Vishkin (1984) consider the relationship in Section 7.6 between uniform families of circuits and PRAM's. Exercise 7.5.6 is from Adleman (1978). Hong (1985) discusses farther the relations between complexity classes.

Cook (1983), Cook (1981), Kindervater and Lenstra (1985), and Johnson (1983) offer reviews of the subject.

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