2. A boolean formula is said to be in Monotone 2-CNF if it is the conjunction of
ID: 3673108 • Letter: 2
Question
2. A boolean formula is said to be in Monotone 2-CNF if it is the conjunction of clauses, each of which has exactly 2 literals and all the literals in the formula are positive (i.e. no negations).
Note that such a formula can be easily satisfied by setting all variables to true.
Consider the following version of the satisfiability problem for Monotone 2-CNF formulas: kMON2SAT = {< , k> | is in Monotone 2-CNF and can be satisfied by setting at most k variables to true}
Prove that k-MON-2SAT is NP-complete.
Explanation / Answer
k-MON-2SAT is easily seen to be in NP, since given an assignment with at most k variables set to true. we can easily verify if it satisfies the formula. To see the NP-hardness, we reduce VERTEX COVER to k-MON-2SAT. Let G = (V, E) be a graph. For each vertex v V , we define a variable xv (with the intention that xv = true iff v is in the vertex cover). Since, for each edge (u, v), at least one vertex must be in the vertex cover, we add the clauses (xu xv) for each edge (u, v) E. The formula is thus given by = ^ (u,v)E (xu xv) Then the formula has a satisfying assignment with k variables set to true if and only if G has a vertex cover of size k.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.