Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Existence of a uniform polynomial-time SAT-CNF decider

Open
VMPvsNP.pa_sat_polytime

by hao jia · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorycomputabilitysat

Does there exist one deterministic multitape machine M, together with positive integers c and k, which correctly decides SAT-CNF on every binary input within the same polynomial bound?

Let L be the language in the shared model: exact Elias-gamma encodings of satisfiable CNF formulas. Invalid encodings are outside L. Let H(M,x,t,b) mean that the actual local machine execution halts by t steps with Boolean answer b. The proposed root statement is

∃M  ∃c,k∈N>0  ∀x∈{0,1}∗  ∃b∈{false,true},H(M,x,cmax⁡(1,∣x∣)k,b)∧(b=true  ⟺  x∈L).\exists M\;\exists c,k\in\mathbb{N}_{>0}\;\forall x\in\{0,1\}^*\;\exists b\in\{\mathrm{false},\mathrm{true}\},\quad H(M,x,c\max(1,|x|)^k,b)\land(b=\mathrm{true}\iff x\in L).∃M∃c,k∈N>0​∀x∈{0,1}∗∃b∈{false,true},H(M,x,cmax(1,∣x∣)k,b)∧(b=true⟺x∈L).

The existential choices precede all inputs: the machine and both constants cannot vary with x. Correctness includes rejecting malformed strings. An oracle, finite-instance success, or a bound measured on an unrelated representation does not meet this target.

Formalization Note The shared module specifies the codec and a finite-description, local-step, two-way multitape machine model. The root item is OPEN and ends with an explicit proof placeholder. Compilation is not a proof, and representation correspondence still requires faithfulness review.

Preamble
import Definitions.Def_VMPvsNP_SATModel
Formal statement
theorem VMPvsNP.pa_sat_polytime :
    ∃ M : VMPvsNP.Machine, ∃ c k : Nat,
      0 < c ∧ 0 < k ∧
      ∀ x : List Bool, ∃ answer : Bool,
        VMPvsNP.HaltsWithin M x (VMPvsNP.polynomialBound c k x) answer ∧
        (answer = true ↔ VMPvsNP.SATCNF x) := by sorry
Source
Stephen Cook, The Complexity of Theorem-Proving Procedures, STOC 1971, pp. 151-158, https://doi.org/10.1145/800157.805047; Clay Mathematics Institute, P vs NP Problem, https://www.claymath.org/millennium/p-vs-np/ . This item states the uniform SAT-CNF root question in the shared explicit model; it is not a theorem asserted to have been proved by those sources.

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me