Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Conditional SAT characterization

Proved
PvsNP.sat_characterization_from_infrastructure

by alexcarter · Sep 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryformalizationp-vs-np

Assuming P inclusion, SAT membership in NP, SAT hardness and closure of P under reductions, equality of P and NP is equivalent to SAT belonging to P.

Status: Local proof checked; unpublished draft statement.

Formal statement
import Definitions.Def_PvsNPFrontier

namespace PvsNP
theorem sat_characterization_from_infrastructure
    (hincl : P ⊆ NP) (hsat : SAT ∈ NP) (hhard : NPHard SAT)
    (hclosed : ∀ A B : DecisionProblem, PReducible A B → B ∈ P → A ∈ P) :
    P = NP ↔ SAT ∈ P := by sorry
end PvsNP
Source
Stephen Cook, The P versus NP Problem, Clay official description, definitions of P/NP and Proposition 1; https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf; Proposition 1, explicit logical deduction.
Read-back

What the Lean code literally says, in plain math · gpt-6-astra

Assume four hypotheses: P⊆NPP\subseteq NPP⊆NP; SAT∈NPSAT\in NPSAT∈NP; ∀L⊆B∗, L∈NP⇒L⪯SAT\forall L\subseteq B^*,\ L\in NP\Rightarrow L\preceq SAT∀L⊆B∗, L∈NP⇒L⪯SAT; and ∀A,B0⊆B∗, A⪯B0⇒B0∈P⇒A∈P\forall A,B_0\subseteq B^*,\ A\preceq B_0\Rightarrow B_0\in P\Rightarrow A\in P∀A,B0​⊆B∗, A⪯B0​⇒B0​∈P⇒A∈P. Under these supplied hypotheses, P=NPP=NPP=NP if and only if SAT∈PSAT\in PSAT∈P. In particular the inclusion, the checker description of SATSATSAT, its incoming reductions, and closure of PPP under the specified reductions are premises of this theorem rather than claims established by its statement. Here B={false,true}B=\{\mathrm{false},\mathrm{true}\}B={false,true}, B∗B^*B∗ is the set of all finite Boolean lists, including the empty list, and ∣w∣|w|∣w∣ is list length. The set PPP consists exactly of languages L⊆B∗L\subseteq B^*L⊆B∗ for which there is a Boolean function χ:B∗→B\chi:B^*\to Bχ:B∗→B satisfying D(χ)D(\chi)D(χ) and ∀w∈B∗, w∈L ⟺ χ(w)=true\forall w\in B^*,\ w\in L\ \Longleftrightarrow\ \chi(w)=\mathrm{true}∀w∈B∗, w∈L ⟺ χ(w)=true. The set NPNPNP consists exactly of languages L⊆B∗L\subseteq B^*L⊆B∗ for which there exist R:B∗×B∗→BR:B^*\times B^*\to BR:B∗×B∗→B and k∈Nk\in\mathbb Nk∈N satisfying C(R)C(R)C(R) and ∀w∈B∗, w∈L ⟺ ∃y∈B∗, ∣y∣≤∣w∣k ∧ R(w,y)=true\forall w\in B^*,\ w\in L\ \Longleftrightarrow\ \exists y\in B^*,\ |y|\le |w|^k\ \land\ R(w,y)=\mathrm{true}∀w∈B∗, w∈L ⟺ ∃y∈B∗, ∣y∣≤∣w∣k ∧ R(w,y)=true. This includes k=0k=0k=0 and empty input: 00=10^0=100=1, whereas 0k=00^k=00k=0 for k>0k>0k>0. Write D(χ)D(\chi)D(χ) for existence of such a machine and a polynomial p∈N[X]p\in\mathbb N[X]p∈N[X] that, for every w∈B∗w\in B^*w∈B∗, compute the singleton output [χ(w)][\chi(w)][χ(w)] from input www in at most p(∣w∣)p(|w|)p(∣w∣) steps. Write C(R)C(R)C(R) for existence of such a machine and a polynomial p∈N[X]p\in\mathbb N[X]p∈N[X] that, for all w,y∈B∗w,y\in B^*w,y∈B∗, compute [R(w,y)][R(w,y)][R(w,y)] in at most p(∣w∣+∣y∣)p(|w|+|y|)p(∣w∣+∣y∣) steps from the list obtained by tagging every bit of www with the left injection into B⊔BB\sqcup BB⊔B, tagging every bit of yyy with the right injection, and concatenating those two lists. For languages A,B0⊆B∗A,B_0\subseteq B^*A,B0​⊆B∗, write A⪯B0A\preceq B_0A⪯B0​ to mean that there exists f:B∗→B∗f:B^*\to B^*f:B∗→B∗ satisfying F(f)F(f)F(f) and ∀w∈B∗, w∈A ⟺ f(w)∈B0\forall w\in B^*,\ w\in A\ \Longleftrightarrow\ f(w)\in B_0∀w∈B∗, w∈A ⟺ f(w)∈B0​. Write F(f)F(f)F(f) for existence of such a machine and a polynomial p∈N[X]p\in\mathbb N[X]p∈N[X] that, for every w∈B∗w\in B^*w∈B∗, compute output list f(w)f(w)f(w) from input list www in at most p(∣w∣)p(|w|)p(∣w∣) steps. Different existential computation witnesses may use different machines and polynomials. A machine in these assertions is a Mathlib TM2 stack machine with finitely many stack indices, instruction labels, and control states, a finite input-stack alphabet, designated input and output stacks, a program, and initial label and control state; its other stack alphabets need not be finite. Input and output alphabet bijections transport the specified encoded lists to the corresponding stack alphabets. Computation starts with only the input stack populated, and reaches a halted configuration with the specified output on the output stack, all other stacks empty, and the control state reset to its initial value. Time counts executions of whole TM2 statements, each of which may contain several stack operations. The language SATSATSAT consists of exactly those w∈B∗w\in B^*w∈B∗ for which there are a formula FFF and an assignment τ:N→B\tau:\mathbb N\to Bτ:N→B such that E(F)=wE(F)=wE(F)=w and every clause of FFF is true under τ\tauτ; strings without such an encoding are excluded. Write E(F)E(F)E(F) for this Boolean-list encoding of a formula FFF: for each literal (b,j)(b,j)(b,j), take [b][b][b] followed by the little-endian canonical binary digits of jjj (the digits of 000 form the empty list), replace each bit ddd by [false,d][\mathrm{false},d][false,d], and append [true,false][\mathrm{true},\mathrm{false}][true,false]; concatenate these literal encodings within each clause and append [true,true][\mathrm{true},\mathrm{true}][true,true]; then concatenate the clause encodings in formula order. In particular E([])=[]E([])=[]E([])=[]. A formula is a finite list of clauses, each clause a finite list of literals (b,j)∈B×N(b,j)\in B\times\mathbb N(b,j)∈B×N. Under an assignment τ:N→B\tau:\mathbb N\to Bτ:N→B, the literal (b,j)(b,j)(b,j) is true exactly when τ(j)=b\tau(j)=bτ(j)=b, a clause is true exactly when some literal in it is true, and a formula is true exactly when every clause is true. Thus an empty clause is false and an empty formula is true.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me