Questions? Call 800-624-6242

| Items in cart [0]

PAPERBACK
price:\$52.75

## Probability and Algorithms (1992) Commission on Physical Sciences, Mathematics, and Applications (CPSMA)

### Citation Manager

. "4 Probabilistic Algorithms for Speedup." Probability and Algorithms. Washington, DC: The National Academies Press, 1992.

 Page 40

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Probability and Algorithms

not speedup exists, and settling this question is likely to be as hard as the notorious ? problem of complexity theory.

There is a weaker sense in which probabilistic algorithms currently offer advantages over deterministic ones. There exist problems for which the fastest known algorithm is probabilistic and problems for which at present the fastest fully analyzable algorithm is probabilistic. Here the situation reflects the current limitations on our knowledge. Section 4.3 describes examples of such problems from number theory, i.e., primality testing and factorization. In both cases, at present, the best fully analyzed algorithms are probabilistic ones.

Probabilistic algorithms give a demonstrable speedup in the exchange of information among several people, each having partial information to begin with. This is the subject matter of communication complexity. It plays an important role in distributed computing, in which exchange of information among the processors is an important part of the computational task. Communication complexity results are described in §4.4.

### 4.2Probabilistic Complexity Classes

The theoretical possibility of speedup has been formalized in computational complexity theory with the notion of probabilistic complexity classes; these classify computational problems according to the running times and types of error allowed by probabilistic algorithms. Here we define several of these complexity classes.

The model of computation used is a probabilistic Turing machine. This is a Turing machine that has an extra "random" tape containing a random string of zeros and ones that can be read as necessary. A probabilistic polynomial-time Turing machine (PPTM) is such a machine equipped with a clock that, when given an input of n bits, always halts after p(n) steps, where p is a fixed polynomial. The performance of such machines is averaged over the uniform distribution of all random bits read by the machine. (At most, p(n) random bits are read during the computation on an n-bit input.) The computational problems considered are those of recognizing a language , where {0, 1}* denotes the set of all finite strings of zeros and ones. For example, might consist of all prime numbers, expressed using their binary representations.

We say that is in the complexity class BPP (bounded-error-probability polynomial time) if there is a PPTM that, given , outputs

 Page 40
 Front Matter (R1-R10) 1 Introduction (1-16) 2 Simulated Annealing (17-30) 3 Approximate Counting Via Markov Chains (31-38) 4 Probabilistic Algorithms for Speedup (39-52) 5 Probabilistic Algorithms for Defeating Adversaries (53-64) 6 Pseudorandom Numbers (65-86) 7 Probabilistic Analysis of Packing and Related Partitioning Problems (87-108) 8 Probability and Problems in Euclidean Combinatorial Optimization (109-130) 9 Probabilistic Analysis in Linear Programming (131-148) 10 Randomization in Parallel Algorithms (149-160) 11 Randomly Wired Multistage Networks (161-174) 12 Missing Pieces, Derandomization, and Concluding Remarks (175-178)