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.

Randomized complexity classes

Due: April 29
Points: 3

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