3-SAT, Independent Set, and the P vs. NP Question

Posted on | In

3-SAT ≤P Independent Set

SAT Problem

Problem 1 (SAT). Given $k$ clauses over $n$ variables: does a satisfying truth assignment exist?

Problem 2 (3-SAT). SAT where each clause has exactly 3 literals.

  • Literal: a variable $x_i$ or its negation $\bar{x}_i$
  • Clause: a disjunction of literals $t_1 \vee \cdots \vee t_\ell$
  • Conflict: $x_i$ and $\bar{x}_i$ conflict with each other

The Reduction

Theorem 1. 3-SAT $\leq_P$ Independent Set.

Proof. From a 3-SAT instance with $k$ clauses, construct graph $G = (V,E)$:

  1. Create $k$ triangles, one per clause. Each vertex of a triangle corresponds to one of the 3 literals in that clause.
  2. Connect pairs of vertices corresponding to conflicting literals with an edge.
  3. Set the target independent set size $k’ = k$.

Example: For $\lbrace (x_1 \vee \bar{x}_2 \vee x_3),\ (\bar{x}_1 \vee \bar{x}_2 \vee \bar{x}_4)\rbrace$, set $k’=2$.

($\Rightarrow$) If 3-SAT is satisfiable: pick one true literal per clause to get $k$ vertices.

  • Exactly one selected per triangle → no edges within triangles.
  • Two conflicting literals cannot both be true → no conflict edges.
  • This is an independent set of size $k$.

($\Leftarrow$) If there is an independent set $S$ of size $\geq k$: since at most one vertex can be selected per triangle, exactly one is chosen per triangle. Assign true to the literals in $S$ (others arbitrary):

  • $S$ cannot contain conflicting vertices → the assignment is consistent.
  • Exactly one vertex per triangle → all clauses are satisfied. ∎

The small components used are called gadgets. Combined with previous reductions:

\[\text{3-SAT} \leq_P \text{Independent Set} \leq_P \text{Vertex Cover} \leq_P \text{Set Cover}\]

Definitions of P and NP

Definition 3. P = the set of decision problems solvable by an efficient (polynomial-time) algorithm.

Definition 4. An efficient certifier $B$ for problem $X$:

  • Takes strings $s$ (instance) and $t$ (hint) as input.
  • Runs in time polynomial in $\lvert s\rvert$ and $\lvert t\rvert$.
  • For every yes-instance $s$: there exists $t$ with $\lvert t\rvert \leq p(\lvert s\rvert)$ such that $B(s,t) = \text{yes}$.
  • For every no-instance $s$: $B(s,t) = \text{no}$ for all $t$.

Definition 5. NP = the set of decision problems for which an efficient certifier exists.

Equivalently, NP is the class of problems solvable by a Nondeterministic polynomial-time algorithm (NP = Nondeterministic Polynomial).

Theorem 2. $\text{P} \subseteq \text{NP}$.

Proof. If $X \in \text{P}$ with algorithm $A$, define $B(s,t)$ = “ignore $t$ and run $A(s)$.” This is an efficient certifier. ∎

Theorem 3. 3-SAT, Independent Set, Vertex Cover $\in$ NP.