Problem 97

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Look up the definitions of the complexity classes RP, ZPP, and BPP in the Complexity Zoo and/or Wikipedia.

Now tell me which of these classes (maybe more than one) do each of the following problems we have studied fall into?

- Telling if two files are the same using a random fingerprint
- Evaluating a game tree (using the randomized algorithm)
- Determining whether a given element is in a set, using a Bloom filter
- Problem 96