Deciding a language within an input-dependent step bound
DefinitionCallCountPOPBR_Supplement_DecidesWithincomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
A language is decided within a bound when one well-formed Cook–Levin multi-tape Turing machine halts on every bit string within machine steps and returns the correct Boolean verdict for .
The definition uses the same machine semantics and step count as the published NP and NP-completeness definitions used by the base mission. It permits to depend on the parameters encoded in , as required for fixed-parameter bounds.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Complexity
set_option autoImplicit false
namespace CallCountPOPBR.Supplement
/-- **Deciding a language within a step bound** (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: "a direct algorithm uses O(q^p N poly(L)) bit operations".
`DecidesWithin L T` holds when one multi-tape Turing machine `M` (the published CookLevin
machines, `k` tapes, alphabet size `G`) decides `L`: on every bit string `w` written on tape 0
(empty tape 1) it halts within `T w` steps with verdict `true` if `w ∈ L` and `false` otherwise.
**Formalization Note.** Time is the step count of the published `CookLevin.execute`, the cost
model under which the base mission states `CookLevin.InNP` / `CookLevin.NPComplete`.
`CookLevin.DecidesIn` evaluates the configuration after exactly `T w` steps; a halted
configuration is a fixed point, so this is "halts within `T w` steps". The bound may depend on the
whole string `w`, not only on its length, so parameterised bounds can be expressed. -/
def DecidesWithin (L : CookLevin.Language) (T : List Bool → ℕ) : Prop :=
∃ (M : CookLevin.Machine) (k G : ℕ), CookLevin.TuringMachine k G M ∧
∀ w : List Bool,
(L w → CookLevin.DecidesIn M k (CookLevin.boolsToSymbols w) [] (T w) true) ∧
(¬ L w → CookLevin.DecidesIn M k (CookLevin.boolsToSymbols w) [] (T w) false)
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