# 2-SAT Problem with additional constraints on variable?

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

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?

• MAX-2SAT is NP-hard, so your problem (which I don't quite understand) is probably not in P. – Yuval Filmus May 4 '17 at 19:21
• 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). – TheoryQuest1 May 4 '17 at 19:27
• Right, it's not MAX-2SAT. Minimum weight 2SAT is probably also NP-hard. – Yuval Filmus May 4 '17 at 19:28