Question

Question 1

a) To show that 3-CNF is NP-complete, we take some NP-complete problem, say SAT, and find a polynomial-time reduction from SAT to 3-CNF. Illustrate a polynomial-time reduction that takes as input an input F of SAT F = (¬x1 ∨ x2 ∨ x3) ∧ (x4 ⇔ ¬x5) and outputs an input f(F) of 3-CNF so that f(F) is a “yes” instance of 3-CNF iff F is a “yes” instance of SAT.

b) Let F be an input to 3-CNF: (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ d) ∧ (¬a ∨ ¬d ∨ ¬b). Show how to transform it into an input (G, j) of Clique such that G has a j-clique iff F is satisfiable. Is F is satisfiable (justify your answer using graph G)?

c) Let F be an input to 3-CNF: (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ d) ∧ (¬a ∨ ¬d ∨ ¬b). Construct an input graph G of 3-Coloring problem such that G can be coloured with 3 colours iff F is satisfiable.

Answer 1