1. A singleton clause in a CNF expression is a clause containing only one literal. Consider...

 

Transcribed Image Text:

1. A singleton clause in a CNF expression is a clause containing only one literal. Consider the following decision problem. SINGLETON CLAUSE SAT (abbreviated SCS) INPUT: a Boolean expression & in CNF which has at least one singleton clause. QUESTION: Is satisfiable? (a) Give a polynomial-time reduction from SAT to SINGLETON CLAUSE SAT. Your main task here is to work out how you can construct, from any CNF ex- pression, a new CNF expression ' which has a singleton clause, such that is satisfiable if and only if ' is satisfiable. Remember that does not necessarily have a singleton clause. The new expres- sion will need to be related to but needs to always have a singleton clause. (b) Prove that, for every CNF expression 4, 4 SAT y' SINGLETON CLAUSE SAT. (c) What else do you need to prove about your reduction from (a), in order to prove that SAT 1. A singleton clause in a CNF expression is a clause containing only one literal. Consider the following decision problem. SINGLETON CLAUSE SAT (abbreviated SCS) INPUT: a Boolean expression & in CNF which has at least one singleton clause. QUESTION: Is satisfiable? (a) Give a polynomial-time reduction from SAT to SINGLETON CLAUSE SAT. Your main task here is to work out how you can construct, from any CNF ex- pression, a new CNF expression ' which has a singleton clause, such that is satisfiable if and only if ' is satisfiable. Remember that does not necessarily have a singleton clause. The new expres- sion will need to be related to but needs to always have a singleton clause. (b) Prove that, for every CNF expression 4, 4 SAT y' SINGLETON CLAUSE SAT. (c) What else do you need to prove about your reduction from (a), in order to prove that SAT

Answer rating: 100% (QA)

a To give a polynomialtime reduction from SAT to SINGLETON CLAUSE SAT you need to provide a way to transform any CNF expression p into a new CNF expre... View the full answer