Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

3-SAT is NP-complete

Statement

The language 3-SAT of satisfiable CNF formulas with exactly three literals per clause is NP-complete.

Facts & Assumptions

Given: An arbitrary Boolean formula φ.

[L1]

The language SAT is NP-complete, by SAT is NP-complete.

[L2]

The Tseitin transformation produces in linear size an equisatisfiable CNF formula whose clauses have at most three literals, by The Tseitin transformation has linear size and preserves satisfiability.

[L3]

A language is NP-complete exactly when it lies in NP and every language in NP polynomial-time many-one reduces to it, by NP-hard and NP-complete languages and Polynomial-time many-one reductions.

Proof

technique · direct
1.1givenconstruct

A truth assignment for a 3-CNF formula can be checked clause by clause in polynomial time, exactly as for SAT. So 3-SAT lies in NP.

1.2L1L2givenconstruct

By [L1], it is enough to reduce SAT to 3-SAT. Start from φ and apply [L2] to obtain an equisatisfiable CNF formula T(φ) whose clauses have size at most three.

2.1step 1.2construct

Replace every 2-clause (ℓ1∨ℓ2) by (ℓ1∨ℓ2∨z)∧(ℓ1∨ℓ2∨¬z) with a fresh variable z, and replace every 1-clause (ℓ) by (ℓ∨u∨v)∧(ℓ∨u∨¬v)∧(ℓ∨¬u∨v)∧(ℓ∨¬u∨¬v) with fresh variables u,v. These replacements preserve satisfiability and produce only 3-clauses.

3.1L2L3step 1.1step 1.2step 2.1∎

Steps 1.2 and 2.1 give a polynomial-time many-one reduction from SAT to 3-SAT, because [L2] is linear-size and the padding in step 2.1 adds only constantly many clauses per short clause. Therefore 3-SAT is NP-hard. Combined with step 1.1, [L3] yields that 3-SAT is NP-complete.

Depends on

Used by

Dependency tree · two levels

14 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources