# 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
clauses and*m*literals in Boolean formula and*n*as an input variable where*g*.*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****n**literals and**m**clauses in CNF form. For MAX-SAT, input function is going to be**f’**with**m’****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 - SAT (in all other assignments) where satisfied clauses are going to be less than
**m,**the

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

- MAX-SAT
**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.