Tuesday, February 10, 2009

Office hours today

Just a reminder that while class is canceled today, I will still be holding my office hours between 12:30pm and 1:30pm today, in Wean 3709. 


  1. This seems a reasonable place for homework hints. Any requests?

  2. Really, no requests? I'm surprised. Guess it was an easy one. Just in case, here are a few hints: 1. completeness. 2. there is subtraction involved. 3. error reduction. 4. Show there is an NP machine N which, on input x, has a surviving branch for each sequence of oracle answers (for the P^NP machine on x) in which all the yes answers are confirmed. After Cook's Theorem, what is the lex-last satisfying assignment for N? 5. already has a hint. 6. already has hint/parts.


Note: Only a member of this blog may post a comment.