The SATISFIABILITY problem is, given a collection of clauses, such as, {(x1 V x2 V x3...

 

Transcribed Image Text:

The SATISFIABILITY problem is, given a collection of clauses, such as, {(x1 V x2 V x3 V x4), (x2 V x3 V x1), (x1 V x4)} assign values to all x; such that each clause evaluates true. This problem reduces to 3-SAT, where each clause has exactly three literals. (a) Show how a single clause that is not in the proper 3-SAT form is made by the reduction into several clauses each in proper 3-SAT. In particular, show the reduction for the following clause: x1 V x2 V x3 V x V x V x6 Name by y; any new variables introduced. (b) Why does your reduction work? Why is the reduced collection of clauses simultaneously satisfiable if and only if the original clause is satisfiable? The SATISFIABILITY problem is, given a collection of clauses, such as, {(x1 V x2 V x3 V x4), (x2 V x3 V x1), (x1 V x4)} assign values to all x; such that each clause evaluates true. This problem reduces to 3-SAT, where each clause has exactly three literals. (a) Show how a single clause that is not in the proper 3-SAT form is made by the reduction into several clauses each in proper 3-SAT. In particular, show the reduction for the following clause: x1 V x2 V x3 V x V x V x6 Name by y; any new variables introduced. (b) Why does your reduction work? Why is the reduced collection of clauses simultaneously satisfiable if and only if the original clause is satisfiable?