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 -SAT of satisfiable CNF formulas with exactly three literals per clause is NP-complete.
Facts & Assumptions
Given: An arbitrary Boolean formula .
The language is NP-complete, by SAT is NP-complete.
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.
A language is NP-complete exactly when it lies in and every language in polynomial-time many-one reduces to it, by NP-hard and NP-complete languages and Polynomial-time many-one reductions.
Proof
A truth assignment for a -CNF formula can be checked clause by clause in polynomial time, exactly as for SAT. So -SAT lies in .
By [L1], it is enough to reduce to -SAT. Start from and apply [L2] to obtain an equisatisfiable CNF formula whose clauses have size at most three.
Replace every -clause by with a fresh variable , and replace every -clause by with fresh variables . These replacements preserve satisfiability and produce only -clauses.
Steps 1.2 and 2.1 give a polynomial-time many-one reduction from to -SAT, because [L2] is linear-size and the padding in step 2.1 adds only constantly many clauses per short clause. Therefore -SAT is NP-hard. Combined with step 1.1, [L3] yields that -SAT is NP-complete.
Depends on
Used by
- CLIQUE is NP-complete Corollary
- Directed and undirected Hamiltonian path and cycle are NP-complete Corollary
- Converting a small Boolean formula to equisatisfiable 3-CNF with extension variables Example
- A constant-query PCP verifier yields constant-gap Max-3SAT Lemma
- Clause-literal consistency graph preserves the Max-3SAT optimum Lemma
- Constant-gap binary CSP is NP-hard Theorem
- Max-3SAT has no PTAS unless P=NP Theorem
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
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
- Stephen A. Cook, The Complexity of Theorem-Proving Procedures (standard reference, not scraped)