↑ Daniel S. Roche
↑ SI 486D
↑ Problems

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

Page maintained by Daniel S. Roche (roche [AT] usna [DOT] edu). Last updated 11 January 2016 14:11.

Material contained above is made available for the purpose of peer review and discussion and does not necessarily reflect the views of the Department of the Navy or the Department of Defense. Some links above are to sites that are not located at the United States Naval Academy. The USNA is not responsible for the content found on these sites. In addition, the content of these sites does not reflect the opinions, standards, policy or endorsement of the Naval Academy or the United States Government.