Published in


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:

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 (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:

Next we must do two steps to prove a problem is NP Complete.

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.

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.

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.

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’

Reverse Implication: If f’ is satisfied then f is satisfied i.e f’ →f

This means that if f is satisfied ↔ f’ is satisfied is correct. That menas SAT -> MAX-SAT reduction can be done in polynomial time.


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.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vincent Tabora

Editor HD-PRO, DevOps Trusterras (Cybersecurity, Blockchain, Software Development, Engineering, Photography, Technology)