Certain situations require a random rather than a deterministic strategy. With a random strategy, the choices are unpredictable and the adversary may be kept off balance. This chapter focuses on the variety and power of randomised algorithms. More specifically, it considers algorithms that find the smallest cut in a graph by combining random vertices until only two remain, or play games by searching the tree of possible moves in random order. It also explains how to check whether the software on a space probe is uncorrupted, how to turn a puzzle with many solutions into one with a unique solution, and how to determine whether two functions are equal. It describes tools such as random hash functions and polynomial identity testing, analyzes the nature of the primes, and looks at a series of randomised algorithms for primality based on different number-theoretic ideas. The chapter concludes by discussing several complexity classes consisting of problems that can be solved using various kinds of randomized algorithms in polynomial time.
Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.