Parameters read from a POPBR input code
DefinitionCallCountPOPBR_Supplement_codeParamscomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
For a bit string , codeParams returns the triple when is the published code of a well-formed POPBR instance with period , maximum offset , and horizon . It returns when is not such a code.
This total parameter map lets the running-time theorem state bounds on every machine input, including malformed strings that the decider must reject.
Formalization Note The published encoding is self-delimiting and injective, so a valid code determines the triple. On a malformed string, for , leaving a polynomial allowance for rejection.
Definition code
import Mathlib
import Definitions.Def_CallCountPOPBR_Instance_code
import Definitions.Def_CallCountPOPBR_Instance_IsValid
set_option autoImplicit false
namespace CallCountPOPBR.Supplement
open scoped Classical
/-- **The parameters `(p, d, N)` read off an input string** (used for Theorem 2.2). Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…),
Definition 2.1 and Theorem 2.2, p.4: "POPBR is fixed-parameter tractable parameterised by p + d.
Writing q = binom(d+1, 2), a direct algorithm uses O(q^p N poly(L)) bit operations."
If `w` is the code `Instance.code I` of a well-formed instance `I` (`Instance.IsValid`), the
value is `(I.p, I.d, I.N)`; on every other string it is `(0, 0, 0)`.
**Formalization Note.** The code is self-delimiting and injective (base definition
`Instance.code`), so the instance, hence the triple, is determined by `w`. Strings that are not
codes of well-formed instances are not instances of the problem; giving them the parameters
`(0, 0, 0)` makes `q^p = 1` there, so a time bound in these parameters still leaves time to read
and reject them. On codes of well-formed instances `d ≥ 1`, so `q = d(d+1)/2 ≥ 1`. -/
noncomputable def codeParams (w : List Bool) : ℕ × ℕ × ℕ :=
if h : ∃ I : Instance, I.IsValid ∧ w = I.code then
((Classical.choose h).p, (Classical.choose h).d, (Classical.choose h).N)
else (0, 0, 0)
end CallCountPOPBR.Supplement
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884…), Definition 2.1 and Theorem 2.2, p.4