Complexity Atlas
HE
a shared fourth literal

3SAT ≤p 4NAE

3SAT≤p4NAE\mathrm{3SAT}\le_p\mathrm{4NAE}, so 4NAE\mathrm{4NAE} is NP-hard. A formula is NAE-satisfiable if some assignment gives every clause both a true literal and a false one.

The construction

On a 3CNF formula φ\varphi with clauses C1,…,CmC_1,\dots,C_m, where Cj=ℓj,1∨ℓj,2∨ℓj,3C_j=\ell_{j,1}\vee\ell_{j,2}\vee\ell_{j,3}:

  1. Pick a single fresh variable zz, shared by all clauses.
  2. For each jj form the four-literal clause Cj′=ℓj,1∨ℓj,2∨ℓj,3∨z.C_j'=\ell_{j,1}\vee\ell_{j,2}\vee\ell_{j,3}\vee z .
  3. Return φ′=⋀j=1mCj′\varphi'=\bigwedge_{j=1}^{m}C_j'.

The intuition: zz acts as a shared ground. Setting z=0z=0 discharges the "some literal is false" requirement in every clause automatically, leaving only "some literal is true" — which is ordinary satisfiability.

Visualization

Guided construction

3SAT → 4NAE

Step 1 of 7
φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
3SAT to 4NAE: clause table with the appended literal zEach row is a clause and each cell a literal, coloured by its value under the current assignment. The fourth column holds the shared fresh literal z. Verdict pills on the right say whether the clause is satisfied and whether it is not-all-equal.φ under v = (1,1,1) — satisfied, but clause 1 is all-trueC₁x₁ = 1x₂ = 1x₃ = 1satisfied ✓all equal ✗C₂¬x₁ = 0x₂ = 1¬x₃ = 0satisfied ✓NAE ✓C₃x₁ = 1¬x₂ = 0¬x₃ = 0satisfied ✓NAE ✓x₁ = 1x₂ = 1x₃ = 1
literal value 1literal value 0

Correctness — both directions

3SAT ∈ ⟹ 4NAE ∈

Suppose vv satisfies φ\varphi. Extend it by v(z)=0v(z)=0 and check it NAE-satisfies φ′\varphi'.

Let Cj′C_j' be an output clause. Since vv satisfies CjC_j, some tt has v(ℓj,t)=1v(\ell_{j,t})=1 — a true literal in Cj′C_j'. And since v(z)=0v(z)=0, the literal zz itself is a false literal in Cj′C_j'. So Cj′C_j' is NAE-satisfied. Hence φ′∈4NAE\varphi'\in\mathrm{4NAE}.

4NAE ∈ ⟹ 3SAT ∈

Suppose φ′∈4NAE\varphi'\in\mathrm{4NAE}, with NAE-satisfying assignment vv. Use the central symmetry of NAE: if vv NAE-satisfies a formula, so does the complementary assignment vˉ\bar v — flipping every value swaps the true literal with the false one in each clause, and both still exist.

So without loss of generality v(z)=0v(z)=0 (otherwise pass to vˉ\bar v). Restrict vv to the variables of φ\varphi. Let CjC_j be a clause of φ\varphi. The clause Cj′C_j' is NAE-satisfied, so it contains a literal evaluating to 11. That literal cannot be zz, since v(z)=0v(z)=0. So some tt has v(ℓj,t)=1v(\ell_{j,t})=1, i.e. CjC_j is satisfied. Hence φ\varphi is satisfiable.

Cost of the reduction

TimeO(|φ|)
SpaceO(|φ|)
Output sizeO(|φ|)

A single pass over the clauses adding one literal each — mm extra literals and exactly one new variable.

What it buys

4NAE\mathrm{4NAE} is NP-hard. Together with 4NAE≤p3NAE\mathrm{4NAE}\le_p\mathrm{3NAE} and transitivity this yields 3SAT≤p3NAE\mathrm{3SAT}\le_p\mathrm{3NAE}, making 3NAE\mathrm{3NAE} the hard starting point for both reductions in lesson 10.

Pitfalls

  • The variable zz is one for the whole formula, not one per clause. With a separate zjz_j per clause the ⇐\Leftarrow direction would lose its symmetry argument — a global flip cannot pin mm different variables to the value you want at once.

  • Complement symmetry is a property of NAE only. It is false for ordinary satisfiability, so the argument does not transfer to non-NAE reductions.

The chain

Used later by

Where this was read from

  • Lesson 10משפט 3: 3NAE\mathrm{3NAE} ו-4NAE\mathrm{4NAE} הן NP-קשות
  • 2024Defining kNAEk\mathrm{NAE} and proving hardness through the NAE family.

  • The lesson assigns both 3SAT≤p4NAE\mathrm{3SAT}\le_p\mathrm{4NAE} and 4NAE≤p3NAE\mathrm{4NAE}\le_p\mathrm{3NAE} as homework and skips the constructions; what it writes out explicitly is only the transitivity computation. The construction above is the standard one and the natural completion, but it is not copied off the board.