Complexity Atlas
HE
the identity map

3SAT ≤p SAT

3SAT≤pSAT\mathrm{3SAT}\le_p\mathrm{SAT}, and therefore 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}.

The construction

On input ⟨φ⟩\langle\varphi\rangle — return ⟨φ⟩\langle\varphi\rangle.

That is the identity map, and that is all of it. This reduction is included precisely because it looks empty: it shows that the direction is the whole claim. This direction — from 3SAT\mathrm{3SAT} to SAT\mathrm{SAT} — says SAT\mathrm{SAT} is at least as hard as 3SAT\mathrm{3SAT}, and it is the easy direction, since every 3CNF formula is in particular a CNF formula. The interesting direction is the other one, and it takes real work.

Correctness — both directions

3SAT ∈ ⟹ SAT ∈

Suppose ⟨φ⟩∈3SAT\langle\varphi\rangle\in\mathrm{3SAT}. Then φ\varphi is a satisfiable 3CNF formula. Every 3CNF formula is in particular a CNF formula, so φ\varphi is a satisfiable CNF formula, i.e. ⟨φ⟩∈SAT\langle\varphi\rangle\in\mathrm{SAT}.

SAT ∈ ⟹ 3SAT ∈

Suppose ⟨φ⟩∈SAT\langle\varphi\rangle\in\mathrm{SAT} where φ\varphi is a 3CNF formula (that is what the input was). Then φ\varphi is satisfiable, and being 3CNF it is in 3SAT\mathrm{3SAT} by definition.

An input that is not a valid encoding of a 3CNF formula is rejected by both languages alike, so it does not break the equivalence.

Cost of the reduction

TimeO(|φ|)
SpaceO(|φ|)
Output size|φ|

Copying time only. The output has exactly the input's length.

What it buys

Together with SAT∈NP\mathrm{SAT}\in\mathrm{NP} and the closure of NP\mathrm{NP} under ≤p\le_p, this gives 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}.

Pitfalls

  • The identity is a legal reduction only when it really preserves both directions. In the same course the identity was rejected as a reduction from 3COL\mathrm{3COL} to 4COL\mathrm{4COL} — there the first direction works and the second collapses. The identity being "trivial" guarantees nothing.

Where this was read from

  • Lesson 8משפט 4: 3SAT≤pSAT\mathrm{3SAT} \le_p \mathrm{SAT}, ומכאן 3SAT∈NP\mathrm{3SAT}\in\mathrm{NP}