3SAT ≤p IS | Complexity Atlas

The construction

On a 3CNF formula $\varphi$ with $m$ clauses:

Vertices. For each clause $C_j$ , create one vertex for every partial assignment satisfying it. A clause of three literals over three distinct variables is satisfied by $7$ of the $8$ partial assignments, so it contributes $7$ vertices.
Edges. Join two vertices whenever their partial assignments conflict — some variable is set $\mathrm{True}$ by one and $\mathrm{False}$ by the other. In particular any two vertices of the same clause are joined, since two distinct satisfying assignments of one clause must differ on some variable; so each clause's vertices form a clique.
Return $\langle G,m\rangle$ .

The intuition: an independent set of size $m$ must take exactly one vertex per clause (each clause is a clique), and the absence of edges among the chosen vertices says exactly that the chosen partial assignments are consistent — so they glue into a single assignment satisfying every clause.

Visualization

φ =(x ∨ y ∨ z)∧(¬x ∨ y ∨ w)∧(¬y ∨ z ∨ w)

Same-clause edgeComplement conflict

Correctness — both directions

3SAT ∈ ⟹ IS ∈

Suppose $\varphi\in\mathrm{3SAT}$ , with satisfying assignment $v$ . For each clause $C_j$ , the restriction of $v$ to the variables of $C_j$ is a partial assignment satisfying $C_j$ , so the graph holds a vertex $u_j$ for it. Set $U=\{u_1,\dots,u_m\}$ .

$|U|=m$ : the vertices belong to different clauses, so they are distinct objects.

$U$ is independent: let $u_j,u_{j'}\in U$ be distinct. Both partial assignments are restrictions of the same $v$ , so on any variable occurring in both they agree — they do not conflict. By construction edges join only conflicting assignments, so $u_ju_{j'}\notin E$ .

Hence $\langle G,m\rangle\in\mathrm{IS}$ .

IS ∈ ⟹ 3SAT ∈

Suppose $\langle G,m\rangle\in\mathrm{IS}$ , with independent set $U$ of size $m$ .

Step 1 — exactly one vertex per clause. Each clause's vertices form a clique, so $U$ holds at most one vertex per clause. There are $m$ clauses and $|U|=m$ , so $U$ holds exactly one per clause. Call it $u_j$ , with partial assignment $\sigma_j$ .

Step 2 — the assignments are consistent. For $j\ne j'$ the vertices $u_j,u_{j'}$ are non-adjacent (as $U$ is independent), so by construction $\sigma_j$ and $\sigma_{j'}$ do not conflict: every variable occurring in both gets the same value.

Step 3 — glue the assignment. Define a total assignment $v$ : if a variable $x$ occurs in some $\sigma_j$ , set $v(x)=\sigma_j(x)$ — by Step 2 this does not depend on which $j$ , so it is well defined; if $x$ occurs in no $\sigma_j$ , set $v(x)=0$ arbitrarily.

Step 4 — $v$ satisfies $\varphi$ . Let $C_j$ be a clause. By construction $\sigma_j$ satisfies it, and $v$ agrees with $\sigma_j$ on every variable of $C_j$ , so $v$ satisfies $C_j$ . As $j$ was arbitrary, $v$ satisfies $\varphi$ , i.e. $\varphi\in\mathrm{3SAT}$ .

Cost of the reduction

TimeO(|φ|²)

SpaceO(|φ|²)

Output sizeO(m²) vertices-pairs, O(m) vertices

The critical point: the bound of $7$ vertices per clause holds only because clause length is bounded. For a general CNF, a clause of length $k$ has $2^k-1$ satisfying assignments — exponential, and the construction would not be polynomial. That is why one starts from $\mathrm{3SAT}$ , not $\mathrm{SAT}$ .

What it buys

$\mathrm{IS}$ is NP-complete, and hence — through $\mathrm{IS}\le_p\mathrm{CLIQUE}$ and $\mathrm{IS}\le_p\mathrm{VC}$ — so are $\mathrm{CLIQUE}$ and $\mathrm{VC}$ .

Pitfalls

The returned threshold is $m$ — the number of clauses, not of variables and not of vertices. That threshold is what forces "one per clause", and without it Step 1 of the backward direction collapses.
The within-clause edges are not an extra rule — they follow from the same rule (conflicting assignments), since two distinct satisfying assignments of one clause must differ on some variable. The construction can be stated as one rule, not two.

The chain

Rests on

SAT ≤p 3SAT

Used later by

IS ≤p VC

Where this was read from

Guided exercisesat-to-independent-set
2024 '1 מועד 1Counting the edges in the reduction's output on $(x_1\vee x_2\vee x_3)\wedge(x_1\vee x_4)$ .
2024 '1 מועד 2The same construction, counted on a different formula.
2025"Prove the construction correct and analyse its running time. Is it polynomial?"

This construction does not appear in the 2026B lessons — there $\mathrm{IS}$ is introduced in lesson 7 and its hardness arrives later by a different route. It is recorded here in the form the exam papers themselves give it (2024 and 2025 both describe it as "the reduction we saw"), so it is mapped to the exam sources and the guided exercise rather than to a lesson.