Problem 42
Show the error in the following fallacious “proof” that P ( NP.
Proof by contradiction. Assume that P = NP. Then SAT ( P. So, of some
k, SAT ( TIME(nk). Because every language in NP is polynomial time
reducible to SAT, NP ( TIME(nk). Therefore P ( TIME(nk). But, by the
time hierarchy theorem, TIME(nk+1) contains a language which isn’t in
TIME(nk), which contradicts P ( TIME(nk). Therefore P ( NP.
Computer Science Homework Solutions
#113569
Automata and Computability
Show the error in the following fallacious “proof” that P NP. Proof by contradiction. Assume that P = NP. Then SAT P. So, of some k, SAT TIME(nk). Because every language in NP is polynomial time reducible to SAT, NP TIME(nk). Therefore P TIME(nk). But, by the time hierarchy theorem, TIME(nk+1) contains a language which isn’t in TIME(nk), which contradicts P TIME(nk). Therefore P NP.
See attached file for full problem description.
What is this?
By OTA - Overall OTA Rating
Maddu Shankar, MSc - 4.6/5
Purchase Cost Now
$2.19 CAD (was ~$19.95)
Included in Download
- Plain text response
- Attached file(s):
- Solution A142.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Automata and Computability - Show that, if P = NP then every language A P except A = 0 and A = * is NP-complete. See attached for full problem description.
- Automata and Computability - Let EQREX = {R,S | R and S are equivalent regular expressions}. Show that EQREX PSPACE. See attached file for full problem description.
- Automata and Computability (A128) - Show that the function K (x) is not a computable function.
- Automata and Computability - Prove that an oracle C exists for which NPC coNPC. See attached file for full problem description.
- Automata and Computability - Describe the error in the following fallacious “proof” that P NP. Consider an algorithm for SAT: “On input , try all possible assignments to the variables. Accept if any satisfy ...
