How To Prove MAX-SAT Is NP Complete
MAX-SAT problem is built on top of the Boolean Satisfiability Problem or SAT. Our premiss is a boolean formula with the following assumptions:
- conjunctive normal form with m clauses
- n literals
- input variable g where g ≤ m
We can then presume that if such a condition exists, then the result is an assignment of the literals such that at least g clauses evaluate to TRUE, otherwise it is FALSE.
How do we prove MAX-SAT is NP Complete?
SAT
SAT (i.e. B-SAT or Boolean SAT) the problem of determining if there exists an interpretation that satisfies a given Boolean formula. It must be able to assign a value to a variable that is either TRUE or FALSE, but it must always evaluate to TRUE.
MAX-SAT is the maximum satisfiability problem in non-deterministic polynomial time.We take the maximum number of clauses that can be satisfied by any assignment and that the given problem minimum clauses satisfied is the value of g.
The MAX-SAT Problem
We describe the following:
- 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 FALSE.
Next we must do two steps to prove a problem is NP Complete.
- Prove that the given MAX-SAT belongs to the NP Class
- The other problems in the NP Class can be polynomial time reducible to that problem (i..e. NP-Hard).
MAX-SAT Belongs To NP Class
In order for proof of being an NP Class, the solution to the problem is verified in polynomial time.
- 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.
- The time complexity is O(n) per clause, and there are m clauses.
- Total running time is O(nm), which is polynomial in nature.
If the three conditions are observed then MAX-SAT belongs to an NP Class.
MAX-SAT is NP-Hard
For the problem to be NP Complete, we must prove it is also NP-Hard. To show that it is NP-Hard, we show that MAX-SAT is a proof of SAT as NP Complete. The problem should be as difficult as the known NP-Complete problem.
This requires a reduction technique for SAT -> MAX-SAT (i.e. input conversion) process.
- For SAT, 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.
- 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 O(1) since we need to map the value of g=m which is polynomial in time.
Next, we need to convert the output from MAX-SAT to output to SAT.
- If MAX-SAT returns FALSE then return FALSE for SAT.
- If MAX-SAT returns the solution as the assignment of literals, then return same solution for all literals.
Assigning values to n literals takes O(n) time, which makes output conversion also polynomial in time.
Proof Of Correctness
We now need to prove the correctness of the problem.
Forward Implication: If f is satisfied then f’ is satisfied i.e f →f’
- SAT i.e f is satisfied then m clauses are set to be TRUE and since g=m in MAX-SAT, m clauses are satisfied in f’. Hence MAX-SAT would also be satisfied.
- SAT (in all other assignments) where satisfied clauses are going to be less than m, the MAX-SAT will not be satisfied.
Reverse Implication: If f’ is satisfied then f is satisfied i.e f’ →f
- MAX-SAT i.e f’ is satisfied, then g=m clauses are satisfied.
- SAT needs to have m clauses satisfied, SAT will also be satisfied.
This means that if f is satisfied ↔ f’ is satisfied is correct. That menas SAT -> MAX-SAT reduction can be done in polynomial time.
Synopsis
MAX-SAT is NP-Hard, if the solution presented can easily lead to the boolean satisfiability problem which is NP Complete. The problem can be verified in polynomial time complexity.
