Problem 34
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 (.” This
algorithm clearly requires exponential time. Thus SAT has exponential
time complexity. Therefore SAT is not in P. Because SAT is in NP, it
must be true that P is not equal to NP.
Computer Science Homework Solutions
#113204
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 .” This algorithm clearly requires exponential time. Thus SAT has exponential time complexity. Therefore SAT is not in P. Because SAT is in NP, it must be true that P is not equal to NP.
What is this?
By OTA - Overall OTA Rating
Maddu Shankar, MSc - 4.6/5
Purchase Cost Now
$2.19 CAD (was ~$15.96)
Included in Download
- Plain text response
- Attached file(s):
- Solution A134.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 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 languag ...
- 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 - Let C be a language. Prove that C turing-recognizable if a decidable language D exists such that C = {x | y (x,y D)}.
- Automata and Computability (A128) - Show that the function K (x) is not a computable function.
- Automata and Computability (A125) - 1. Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof) that prints itself out.
