0
$\begingroup$

MAX 2SAT is NP complete.

Instead of satisfying the maximum number of clauses, I have a fully satisfiable 2SAT formula and I want to have the maximum number of positive literals in the assignment (such that all the clauses are satisfied, of course).

What is the difficulty of this problem?

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you edit the question to clarify what you mean? What do you mean by "positive literals in the assignment"? An assignment maps from variables to {True,False}. There are no literals in an assignment. $\endgroup$ – D.W.♦ May 20 '20 at 4:57
  • $\begingroup$ As a remark to the OP, I added two possible interpretations in a comment to Laakeri's answer. Maybe those could be helpful when editing the question :) $\endgroup$ – Bernardo Subercaseaux May 20 '20 at 5:37
  • $\begingroup$ I mean if I choose a standard assignment {True,False,True,True,True,False...} how close can I get to this assignment (the number of variables assigned the same way). If I flip the literals in the formula that must be False I can reduce this to the problem where a maximum must be True, then I ask in the question if this can be solved. I don't know how to clarify it though. $\endgroup$ – d3m4nz3 May 20 '20 at 7:28
2
$\begingroup$

This problem is NP-hard (and in addition hard to approximate and W[1]-hard), because maximum independent set can be reduced to it. Reduction: Each variable represents a vertex and each clause represents an edge.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Maybe I'm missing something, it seems that the OP wants to assign "true" to the maximum number of variables that appear as positive literals in the formula. If we interpret that as "only appear as positive literals" then the problem is in P, as 2-SAT formulas are monotone with respect to variables that appear only as positive literals. If we interpret it as "appear at least once as positive literals", then the formula given by the conjunction of $(\bar{x_u} \lor \bar{x_v})$ for every edge $(u,v)$ and $(x_1 \lor x_2 \ldots \lor x_n)$, works as reduction from MIS. Still upvoted your answer. $\endgroup$ – Bernardo Subercaseaux May 19 '20 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.