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.
SAT is NP-complete
Statement
The satisfiability language is NP-complete.
Facts & Assumptions
Given: A language .
The language lies in , by SAT lies in NP.
The verifier and nondeterministic-machine definitions of agree, by The verifier and nondeterministic definitions of NP agree.
For a fixed nondeterministic polynomial-time machine, the Cook-Levin formula is satisfiable exactly when an accepting bounded tableau exists and is computable in polynomial time, by The Cook-Levin formula is satisfiable if and only if an accepting bounded tableau exists and The Cook-Levin reduction map is computable in polynomial time.
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
By [L1], is in . To prove NP-completeness via [L4], it remains to prove NP-hardness.
Because , [L2] supplies a nondeterministic polynomial-time machine deciding . For an input , let be the Cook-Levin formula for a polynomial bound on computations of on .
By [L3], the formula is satisfiable exactly when has an accepting bounded tableau on ; with the bounded-tableau convention that later rows may repeat a halting configuration, this happens exactly when . The same citation shows that is computable in polynomial time. Therefore .
Since was arbitrary, step 2.1 proves that every language in reduces to . Together with step 1.1, [L4] gives that is NP-complete.
Depends on
Used by
- 3-SAT is NP-complete Theorem
- CircuitSAT is NP-complete Theorem
Dependency tree · two levels
17 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
- MIT 18.404J / 6.840J, Lecture 16: Cook-Levin Theorem (standard reference, not scraped)
- Stephen A. Cook, The Complexity of Theorem-Proving Procedures (standard reference, not scraped)