Given a 2-SAT problem that is satisfiable. The solution to the problem can be found in polynomial time.

Adding an additional constraint:

  1. The maximum number of positive literals that can have the boolean Value 1 is N. (i.e. a=positive literal, ~a=negative literal)

Is the problem still solvable in Polynomial time?

My assumption is it should be but I am unclear now to modify the original solution? Or are we looking at something similar to the Vertex Cover Problem?

  • $\begingroup$ MAX-2SAT is NP-hard, so your problem (which I don't quite understand) is probably not in P. $\endgroup$ May 4 '17 at 19:21
  • $\begingroup$ Much thanks. The problem is satisfiable. Thus we can easily solve it. But the solution is required to have an additional constraint that it can have at most N 1's. For example lets assume that all of the following solutions to a given hypothetical 4 variable problem are valid: (1) A=0, B=0, C=1, D=0 (2) A=1, B=0, C=0, D=1 (3) A=0, B=0, C=0, D=1. If N=1 is the condition only (1) and (3) can be valid solutions but not (2). $\endgroup$ May 4 '17 at 19:27
  • 1
    $\begingroup$ Right, it's not MAX-2SAT. Minimum weight 2SAT is probably also NP-hard. $\endgroup$ May 4 '17 at 19:28

That is NP-hard by reduction from vertex cover, even when there are no negative literals.
If you meant to count by occurrences rather than just bounding the number of
distinct variables which are true, then use this paper's result and this paper's result.


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.