Georgia Institute Of Technology CS 6515 HW7_solutions.

Document Content and Description Below

CS 6515 – HW 7. Name: 1 Problem 1 (Almost-SAT) Solution: To prove that Almost-SAT is NP-complete we have to show it is in the class NP and it is NP-hard. We show it is NP first. Given an input f... in conjunctive normal form and a candidate solution, we proceed to evaluate each clause while keeping track of the number of clauses that evaluate to TRUE. Each evaluation takes at most. O(n) hence the entire checking takes O(nm), which is polynomial. We conclude Almost-SAT is in NP. To show it is NP-hard, we reduce SAT to it. Given an input f of SAT, in conjunctive normal form, we create an input f0 of Almost-SAT by adding a new variable y and two new clauses: f0 = f ^ (y) ^ (¯ y): This transformation takes O(1) time, so it is polynomial. Notice that any assignment of the new variable y satisfies exactly one of the two new clauses. This observation implies that any solution of Almost-SAT must evaluates TRUE all clauses in f, hence leading to a solution of SAT if we disregard the new variable y. Clearly, from a solution of SAT we can build a solution of Almost-SAT by taking the same assignment of the old variables and putting y =TRUE. This completes the reduction and establish that Almost-SAT is NP-complete. [Show More]

Last updated: 1 year ago

Preview 1 out of 2 pages