Prove that the problem SAT, which takes an arbitrary Boolean formula S as input and asks whether S is satisfiable, is NP-complete. If you are proving a problem is in NP-Complete, you must - 

a. Prove that the problem is in NP (state the verification problem, give and explain an algorithm to verify a certificate in polynomial time, and prove its runtime is polynomial time).

b. Prove the problem is in NP-Hard. Do this by giving a reduction of an NP-complete problem and proving that it reduces to the unknown (the problem you are proving to be in NP-complete) problem in polynomial time. Then, reduce the unknown to the known given problem in polynomial time. Remember that within the proof of correctness of the reduction to prove in both directions (it is an if and only if).

Answer rating: 100% (QA)

To prove that the Boolean satisfiability problem SAT is NPcomplete we need to a Prove that SAT is in NP The verification problem for SAT is to check w... View the full answer