Polynomial-time decidability in the Cook–Levin machine model
DefinitionCallCountPOPBR_Supplement_InPcomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
A language belongs to when one Cook–Levin multi-tape Turing machine decides every input within
steps for some constants .
This definition supplies the polynomial-time clauses of Theorem 2.2 in the same cost model used by the base mission.
Definition code
import Definitions.Def_CallCountPOPBR_Supplement_DecidesWithin set_option autoImplicit false namespace CallCountPOPBR.Supplement /-- **Polynomial-time solvability (the class P)** (used for Theorem 2.2). Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Theorem 2.2, p.4: "for each fixed p the problem is polynomial-time solvable". A language is in P when some multi-tape Turing machine decides it within `c · (|w| + 1)^e` steps on every input `w` (`CookLevin.polyBound c e |w|`), for constants `c, e`. **Formalization Note.** Same machine model and step count as the published `CookLevin.InNP`. -/ def InP (L : CookLevin.Language) : Prop := ∃ c e : ℕ, DecidesWithin L (fun w => CookLevin.polyBound c e w.length) end CallCountPOPBR.Supplement
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884…), Theorem 2.2, p.4