Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Every total polynomial-time SAT-CNF candidate has an error input

Open
VMPvsNP.pn2_sat_no_polytime_decider

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

complexity-theorycomputabilitysat

Does every total uniformly polynomial-time Boolean-answering deterministic multitape machine have an input on which it gives the wrong SAT-CNF answer?

Let L be the shared binary SAT-CNF language, including rejection of malformed encodings. Let H(M,y,t,b) denote actual local execution halting by t transitions with Boolean answer b. For every machine M and positive integers c and k, the target is

(∀y∈{0,1}∗  ∃b∈{false,true}, H(M,y,cmax⁡(1,∣y∣)k,b))⟹(∃x∈{0,1}∗  ∃b∈{false,true}, H(M,x,cmax⁡(1,∣x∣)k,b)∧¬(b=true  ⟺  x∈L)).\left(\forall y\in\{0,1\}^*\;\exists b\in\{\mathrm{false},\mathrm{true}\},\ H(M,y,c\max(1,|y|)^k,b)\right)\Longrightarrow\left(\exists x\in\{0,1\}^*\;\exists b\in\{\mathrm{false},\mathrm{true}\},\ H(M,x,c\max(1,|x|)^k,b)\land\neg(b=\mathrm{true}\iff x\in L)\right).(∀y∈{0,1}∗∃b∈{false,true}, H(M,y,cmax(1,∣y∣)k,b))⟹(∃x∈{0,1}∗∃b∈{false,true}, H(M,x,cmax(1,∣x∣)k,b)∧¬(b=true⟺x∈L)).

Total bounded halting is a premise, but correctness and assumed failure are not. The error input may depend on M, c, and k; one common witness for every candidate is not required. A failure of one algorithm or a restricted model does not settle this universal target.

Formalization Note PA and PN2 import the same published definitions. This is an OPEN root statement with an explicit proof placeholder, not a root proof or an admitted P-versus-NP conclusion. The concrete representation correspondence remains subject to faithfulness review.

Preamble
import Definitions.Def_VMPvsNP_SATModel
Formal statement
theorem VMPvsNP.pn2_sat_no_polytime_decider :
    ∀ M : VMPvsNP.Machine, ∀ c k : Nat,
      0 < c → 0 < k →
      (∀ y : List Bool, ∃ answer : Bool,
        VMPvsNP.HaltsWithin M y (VMPvsNP.polynomialBound c k y) answer) →
      ∃ 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