plz answer this qusetion clearly 2. Now recall each k-CNF formula has at most k

Question

plz answer this qusetion clearly

2. Now recall each k-CNF formula has at most k literals per clause and that the set k-SAT consists of those k-CNF formula that are satisfiable by some truth assignment to their variables. Consider the following mapping from 2-COLOR to 2-SAT Map every vertex z of a graph G onto a Boolean variable X. For each edge (u, v) in G, add clauses (U + V)(U + V) to an initially-empty CNF formula F. G is 2-colorable if ad only if F is 2-satisfiable. Prove that this is a correct many-one reduction between the two problems

Explanation / Answer

Many-one reductions map instances of one problem to instances of another.

consider an edge (u,v) in G , according to graph coloring problem these two vertices should have different colors.

Suppose if the two vertices have same color ,

      let U= V = 0, then (U + V) will not get satisfied and the formula will not remain satisfiable

      let U = V = 1 then (U' + V') will not get satisfied and the formula will not remain satisfiable

Suppose if the two vertices have different color,

     let U = 0 , V= 1 or U=1 , V=0 then both (U+V) and (U' + V') will get satisfied.

This means that if graph is colorable then the formula becomes satisfiable.

If we can check whether the formula is satisfiable or not then we can solve the graph coloring problem also.

Hence the given reduction is correct mapping reduction.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.