Proof that MAX-SAT is NP Complete

Prerequisite: NP-Completeness, NP Class, SAT 

Problem: The MAX-SAT problem which is built on top of SAT(Boolean Satisfiability Problem) problem takes a boolean formula in conjunctive normal form with m clauses, n literals and input variable g where g ≤ m. If such an assignment exists, the result is an assignment of the literals such that at-least g clauses evaluate to TRUE, otherwise NO. Demonstrate that MAX-SAT is NP-Complete.

Explanation:

SAT , sometimes called as B-SAT(Boolean Satisfiability Problem)which is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.It asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE

MAT-SAT is the maximum satisfiability problem, is an FNP generalisation of SAT. It asks for the maximum number of clauses which can be satisfied by any assignment and for the given problem minimum clauses satisfied should be g.

Given MAX-SAT problem can be described as follows:

Input –  Conjunctive normal forms of m clauses and n literals in Boolean formula and g as an input variable where g ≤ m.
Output –  If at-least g clauses are evaluated to TRUE, then assignment of literals is returned, otherwise NO.

To prove a problem NP Complete , there are two steps involved:

1. Prove given problem belong to NP Class
2. All other problems in the NP class can be polynomial time reducible to that problem. (This is the prove of being NP-Hard)

Now it is not possible to reduce every NP problem to another NP problem to prove it’s NP completeness all the time. That’s why we show that any known NP complete problem is reducible to that problem in polynomial time.

Proof:

To solve MAX-SAT as an NP-complete problem, we need to prove above two steps.

1. MAX-SAT belongs to NP Class: A problem is classified to be in NP Class if the solution for the problem can be verified in polynomial time.

• So, given input I to MAX-SAT and a solution S, we can check whether each literal is evaluated to TRUE/FALSE, and there are n literals in a clause.
• So time complexity is O(n) per clause, and there are m clauses.
• So total running time is O(nm), which is polynomial in nature. So MAX-SAT belongs to the NP Class.

2. MAX-SAT is an NP-Hard Problem:

Now we need to show that MAX-SAT is as hard as a known NP-Complete Problem. By using a reduction strategy we can show that MAX-SAT is as least as difficult as a known NP-Complete Problem (the known problem here will be the SAT problem). See here for the “Proof of SAT Is an NP-Complete“.

We are going to show the reduction from SAT -> MAX-SAT

Input Conversion: We need to convert the input from SAT to input to MAX-SAT. 

• For SAT, we are given a function f with n literals and m clauses in CNF form. For MAX-SAT, input function is going to be f’ with m’ clauses and n’ literals and integer g.
• To transform the given input from SAT -> MAX SAT
  • Take input from SAT problem in CNF form f having n literals and m clauses.
  • Set g = m

The transformation is going to be O(1) as we need to map the value of g=m so input conversion is polynomial in time.

Output Conversion: We need to convert the output from MAX-SAT to output to SAT

• If MAX-SAT returns NO then return NO for SAT.
• If MAX-SAT returns the solution as an assignment of literals, then return the same solution for all literals

So, assigning values to n literals takes O(n) time. So output conversion is polynomial in time.

Correctness: Now we need to prove the correctness of the claim which says

f is satisfied ↔ f’ is satisfied

• Forward Implication: f is satisfied  then f’ is satisfied  i.e f →f’ 
  • For a given assignment in which SAT i.e f is satisfied will have m clauses set to be TRUE and since g=m in MAX-SAT so at least m clauses need to be satisfied in f’. Hence MAX-SAT would also be satisfied. 
  • And in all other assignments of SAT where the number of satisfied clauses is going to be less than m then MAX-SAT is not going to be satisfied.
• Reverse Implication: f’ is satisfied then f is satisfied i.e f’ →f
  • For a given assignment in which MAX-SAT i.e f’ is satisfied, we will have at least g=m clauses be satisfied and 
  • For SAT we need to have m clauses to be satisfied. Hence SAT would also be satisfied.

So, this means if claim f is satisfied ↔ f’ is satisfied is correct.

Hence, SAT -> MAX-SAT reduction can be done and takes polynomial time. 

Conclusion:

So MAX-SAT is seen to be a generalisation of SAT and it’s also NP-Complete.