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.
This seems a reasonable place for homework hints. Any requests?
ReplyDeleteReally, 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.
ReplyDelete