PropositionStatement: 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.

SAT lies in NP

Statement

The satisfiability language $S A T$ belongs to $N P$ .

Facts & Assumptions

Given: A Boolean formula $φ$ with variables among $x_{1}, \dots, x_{n}$ .

[L1]

The language $S A T$ consists exactly of the encodings of satisfiable Boolean formulas, by Boolean formulas, conjunctive normal form, and the satisfiability language SAT.

[L2]

A language lies in $N P$ when membership can be verified in polynomial time from a polynomially bounded certificate, by The class NP via polynomial-time verifiers and Polynomial-time verifiers with polynomially bounded certificates.

Proof

technique · direct

1.1

Use as certificate a truth assignment $a \in {0, 1}^{n}$ for the variables of $φ$ . Its length is $n$ , so it is linearly bounded by the input size of $⌜ φ ⌝$ .

L2givenconstruct

2.1

A deterministic verifier can evaluate $φ$ under $a$ by traversing the parse tree of $φ$ once. That takes time polynomial in $∣ ⌜ φ ⌝ ∣$ , and by [L1] it accepts exactly when $φ$ is satisfiable. Therefore [L2] gives $S A T \in N P$ .

L1L2step 1.1∎

Depends on

Used by

3-SAT is NP-complete Theorem
SAT is NP-complete Theorem

Dependency tree · two levels

5 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)