Theorem 2.2 — FPT completion and reconstruction
OpenCallCountPOPBR.Supplement.theorem_2_2complexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science
Let be the parameters read from a well-formed POPBR code , and on a malformed string. Put . There is one Cook–Levin multi-tape Turing machine deciding POPBR on every bit string such that all four conclusions hold:
- for a computable function and an absolute exponent , its running time is at most ;
- for absolute constants , its running time is at most
- for every fixed period , POPBR restricted to codes with is in , while remains part of the input;
- for every fixed , POPBR restricted to those parameter values is in with arbitrary missing observations.
This is the algorithmic upper bound that separates fixed-period instances from the variable-period NP-completeness result.
Formalization Note The same Cook–Levin machine model underlies the base mission's definitions of NP and NP-completeness.
Differences from the source:
- reading: bit operations → one Cook–Levin multi-tape Turing machine with absolute constants and the displayed step bound; reason: machine steps are the platform cost model, and the polynomial overhead of bit operations is absorbed by
- encoding: the source defines parameters only for valid instance codes and uses the factor → malformed strings have and the total bound uses ; reason: a decider must also read and reject malformed strings, while is asymptotically the same factor on instances
Preamble
import Mathlib import Definitions.Def_CallCountPOPBR_POPBR import Definitions.Def_CallCountPOPBR_Supplement_DecidesWithin import Definitions.Def_CallCountPOPBR_Supplement_InP import Definitions.Def_CallCountPOPBR_Supplement_codeParams set_option autoImplicit false
Formal statement
namespace CallCountPOPBR.Supplement
/-- **Theorem 2.2 (FPT completion and reconstruction).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), 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. In particular, for each fixed p the problem is polynomial-time
solvable, even when d is part of the input; for fixed p, d it is polynomial-time solvable with
arbitrary missing observations."
With `(p, d, N) = codeParams w` and `q = d(d+1)/2`:
1. (FPT) some computable `f` and constant `c` such that POPBR is decided within
`f(p + d) · (|w| + 1)^c` steps;
2. (explicit bound) absolute constants `C, c` such that POPBR is decided within
`C · q^p · (N + 1) · (|w| + 1)^c` steps;
3. for every fixed `p₀`, POPBR restricted to instances with `p = p₀` (`d` arbitrary) is in P;
4. for every fixed `p₀, d₀`, POPBR restricted to instances with `p = p₀`, `d = d₀` (any
observations) is in P.
**Formalization Note.** "Bit operations" are steps of the published CookLevin multi-tape Turing
machines; `O(·)` and `poly(L)` become constants `C, c` fixed before the input. The factor `N` is
`N + 1` (positive on non-codes). -/
theorem theorem_2_2 :
(∃ (f : ℕ → ℕ) (c : ℕ), Computable f ∧
DecidesWithin POPBR (fun w => f ((codeParams w).1 + (codeParams w).2.1) * (w.length + 1) ^ c)) ∧
(∃ C c : ℕ, DecidesWithin POPBR (fun w =>
C * ((codeParams w).2.1 * ((codeParams w).2.1 + 1) / 2) ^ (codeParams w).1 *
((codeParams w).2.2 + 1) * (w.length + 1) ^ c)) ∧
(∀ p₀ : ℕ, InP (fun w => POPBR w ∧ (codeParams w).1 = p₀)) ∧
(∀ p₀ d₀ : ℕ, InP (fun w => POPBR w ∧ (codeParams w).1 = p₀ ∧ (codeParams w).2.1 = d₀)) := by sorry
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