3-SAT

3-SAT (Theorem Cook-Levin)

Input: A CNF-formula in which each clause has at most three literals.

Output: (the answer to the question) is there a truth assignment to the variables that satisfies all the clauses?

SAT problem for this Boolean expression: is there such values of 𝑥1,𝑥2,𝑥3, that given Boolean expression is TRUE. The answer to SAT problem is only YES or NO. We don’t care what’s the values of 𝑥1,𝑥2,𝑥3, just existence of such values.

It is a special case of SAT. Divided in clauses, such that every clause contains 3 literals.

For example: $(x_1\vee x_2\vee x_3)\wedge (x_4\vee x_5\vee x_6)$

If we can prove 3-SAT ${\le }_{P}X$, then $X$ is NP-Complete. For example $IS\in$ NPC, since 3-SAT${\le }_{P}IS$. (We can reduce 3-SAT to independent set).

To prove that a problem $X\in$ NP is NP-complete, we just need to find a NP-complete problem $Y$, and prove that $Y{\le }_{P}X$.

Proof Outline

Reduction from 3-SAT to IS:

• Given a 3-SAT formula, construct a graph where each variable $x_i$ corresponds to a vertex in the graph.
• For each variable $x_i$, create two vertices: $x_i$ and $\overline{x_i}$, representing the true and false assignments respectively.
• Connect the vertices corresponding to the literals in each clause. If a clause contains a literal $x_i$, connect the vertices corresponding to $x_i$ and $\overline{x_i}$ to the vertices corresponding to the other literals in the clause. This ensures that if one literal in the clause evaluates to true, the clause can still be satisfied.
• Ensure that vertices representing literals within the same clause are not connected directly. This prevents assigning conflicting truth values to literals within the same clause. The resulting graph represents a collection of disjoint sets of vertices, each set representing a clause in the 3-SAT formula.
• The objective is to find an independent set in this graph, where no two vertices in the set are adjacent. This corresponds to finding a truth assignment to the variables that satisfies all the clause in the 3-SAT formula.

Circuit Satisfiability