Question

Show that the following problem is NP-hard.

Input: A boolean function in CNF such that every clause has at most three literals and every variable appears in at most three clauses.

Output: An assignment that evaluates the given function TRUE.

Answer 1

Now consider the Almost-SAT problem which is defined below:

Input: A CNF formula F having m clauses in n variables x1, x2, . . . , xn. There is no
restriction on the number of variables in each clause.
• Output: YES if there is an assignment to the variables which satisfies exactly m − 1
clauses, and NO otherwise.
For example, given the boolean formula F to be
F = (x1 ∨ x2) ∧ (x1 ∨ x¯3 ∨ x¯4 ∨ x5) ∧ (¯x2) ∧ (x2 ∨ x5)
Here is one assignment to the variables which satisfies all four clauses: x1 = T, x2 = F, x3 =
F, x4 = T, x5 = T. So the expected output of SAT on this example will be YES.
This formula also has an assignment which satisfies exactly 3 of the 4 clauses: x1 = T, x2 =
T, x3 = F, x4 = T, x5 = T. So the expected output of Almost-SAT on F is also YES.
The goal of this problem is to show that Almost-SAT is NP-complete.
We will first prove that Almost-SAT is in NP. A problem is said to be in NP
if a solution to the problem can be verified in polynomial time. Give a polynomial time
algorithm which takes as input an assignment to each variable, and verifies whether it is a
solution to Almost-SAT or not.
SOLUTION:
Loop through all the clauses and check whether each of them is satisfied. Maintain a global
counter, and check whether it equals to m − 1 at the end.
This algorithm runs in poly time because there is at most m clauses.