Note: I've also asked this question on StackOverflow here
I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard.
However, if you see the article, I'm not able to understand why, after
ci is satisfied, 7 out of 10 clauses are satisfied and if it is not satisfied, the 6 out of 10 clauses are satisfied.
Can someone explain to me in simple terms, and demystify what exactly the article wants to convey? Essentially, I have come to know that a max-2-sat problem is the same as a 3 sat problem. The question is I'm not able to understand why.
More formally, I wish to solve this problem:
Consider the problem MAX2SAT described as follows.
Given a 2-CNF (Conjunctive Normal Form) Boolean expression (with m clauses, n variables) and an integer k, Decide if there is an assignment satisfying at least ‘k’ of the total clauses? Compute the complexity class (P or NP or NP Complete) of the MAX2SAT with justification.