HW#5 --- last modified January 01 1970 00:00:00..
Due date: May 7
Purpose: To get more familiar with probabilistic complexity classes, circuit classes, and to start learning a little about complexity related to cryptography.
Specification:
Do the following problems 11.5.16, 12.3.7, 14.5.9, 17.3.8 out of the book
then solve:
5. Exhibit an oracle A under which NP ∩ coNP has complete problems,
yet NPA=/=PA.
Point Breakdown
| Each problem is worth 2pts |
10pt
|
| Total |
10pts |
|