It might be helpful to ponder exercises 6/7 in the notes. Specifically:

  • Show that there is an oracle A and a language L \in NP^A such that L is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to A
  • Suppose we pick a random language B, by deciding for each string independently and with probability 1/2 whether or not it is in B. Show that with high probability P^B \ne NP^B
Advertisements