15 A Simple reduction - Almost SAT

SAT

Given a CNF formula with $N$ variables and $M$ clauses:

• SAT: Can we satisfy all $M$ clauses ?
• Almost SAT: Can we satisfy exactly $M-1$ clauses ?

Reduction

• Let the instance of SAT have the variables $x_1,x_2,\cdots ,x_N$
• Want to create an instance of Almost SAT such that
  • (i) All clauses of SAT are satisfied $\Rightarrow$ all but one clause of Almost-SAT are satisfied.
  • (i) All clauses of SAT are satisfied $\Leftarrow$ all but one clause of Almost-SAT are satisfied.
• Hint: For any variable $y$, exactly one of the clauses $y$ or $\neg y$ is satisfiable!
• Let $I$ be an instance of SAT and we can build an $I^{\prime }$ instance of Almost-SAT such that:
• $I^{\prime }=I\wedge (y)\wedge (\neg y)$
• No matter what truth assignment is picked for $y$ only one of them is satisfied.
• So, the reduction clearly works in polytime