Sipser 10.1-10.2

Read Sipser §10.1 and §10.2

  1. Section 10.1 gives several examples of optimization problems, along with algorithms to approximate their solutions. Give another example of an optimization problem that is undecidable – meaning an approximation algorithm might be an appropriate application.
  2. Describe the choice of 1/3 in the definition of BPP, and why this choice is OK even though it seems like quite a large margin of error.
  3. Describe, in your own words, the difference between the classes BPP and RP.
css.php
The views and opinions expressed on individual web pages are strictly those of their authors and are not official statements of Grinnell College. Copyright Statement.