Existence of a uniform polynomial-time SAT-CNF decider
OpenVMPvsNP.pa_sat_polytimeDoes 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
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.
import Definitions.Def_VMPvsNP_SATModel
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