Practice Problem: Almost-SAT

1. Problem Statement

Consider the Almost-SAT problem defined as following:

Input: A CNF formula $f$ with $n$ variables $x_1, … , x_n$ and $m$ clauses.

Output: An assignment that satisfies exactly $m - 1$ clauses, or NO if no such assignment exists.

Now, our aim is to prove that Almost-SAT problem is NP-Complete.

2. Attack Plan

In order to prove that Almost-SAT $\in$ NP-Complete, we need to show two things:

1. First of all, we need to make sure that Almost-SAT is a search (or decision) problem, i.e. Almost-SAT $\in NP$
2. Second, we want to make sure that Almost-Sat is NP-Hard (at least as hard as any of NP-Complete problems).

3. Proof

3.1 Almost-SAT $\in$ NP

Being a search/decision problem, means we have a polynomial time algorithm that can verify validity of a solution.

Thus, given input $f$ for Almost-SAT and an assignment $S$ (which is a proposed solution):

• in $O(n)$ we can verify that any particular clause is satisfied or not

• we have $m$ clauses, so $O(mn)$ time to check that exactly $m - 1$ clauses are satisfied

3.2 SAT $\to$ Almost-SAT

Consider some problem $B$ which is NP-Complete. Being NP-Complete means $$A \to B, \forall A \in NP$$ That’s $B$ is as hard as any problems in NP.

From this, notice that $$(A \to B) \land (B \to C) \implies A \to C$$

This means, given a known NP-Complete problem ($B$ above), it is enough to reduce that problem to Almost-SAT, to prove that Almost-SAT is NP-Complete too.

By Cook-Levin Theorem we know that SAT is NP-Complete.

Let’s reduce SAT to Almost-SAT, to complete the proof.

• Consider input for SAT problem: a CNF formula $f$ of $n$ variables and $m$ clauses.
• Create a new variable $v$, and use it to define a new formula $f’ = f \land (v) \land(\bar{v})$.
• Note that $m’ = m + 2$ (where $m'$ is number of clauses in $f'$, and $m$ is number of clauses in $f$)

Claim: $f$ is satisfiable $\iff$ $f'$ has an assignment satisfying $m’ - 1$ clauses

Forward implication: take any satisfying assignment for $f$, then set $v = True$, implication follows immediately.

Reverse implication: for a given satisfying assignment of $f'$, only one of clauses $(v)$ or $(\bar{v})$ can be satisfied. So, in the whole formula $f'$, $m’ - 1$ clauses are satisfiable at most. Now, given such an assignemnt, drop variable $v$ from it, and we have satisfactory assignment for $f$.

Since, both transforming $f$ to $f'$ and transforming satisfying assignment for $f'$ to that of $f$ takes polynomial time, SAT $\to$ Almost-SAT. $\blacksquare$