Section 2.1 — the reduction instance
ProvedCallCountPOPBR.reduction_instanceaddition-sequencescomputational-complexitynp-completenessp2o-gran-per-chapterp2o-plan-paperp2o-v1recursion
There is a constant such that for every simple graph on vertices with edges and every :
- the edge enumeration lists each edge (as with ) exactly once;
- is a well-formed instance with , , and , where ;
- the base indices carry no observation; index () is observed with ; the indices () are unobserved; index () is observed with ; and the target block ends at ;
- exactly recursive indices are unobserved;
- and every observed value has at most bits.
Item 5 is the paper's "N = O(n³), so the list encoding of Definition 2.1 has O(n³) entries, each of O(n³) bits".
Differences from the source:
- encoding: V = {1, …, n} and a_v = sv → vertices 0, …, n − 1 of NPGraph.Graph with a_v = s(v + 1); reason: the published graph type numbers vertices from 0; the exponents are the same numbers s, 2s, …, ns
- reading: N = O(n³); O(n³) entries, each of O(n³) bits → ∃ c, ∀ G K, N ≤ c(n + 1)³ and Nat.size v ≤ c(n + 1)³ for every observed v; reason: big-O over all admissible (G, K) with one constant; n + 1 avoids n = 0
- encoding: enumerate the edges as e₁, …, e_m → edgeList G is duplicate-free and lists exactly the pairs (i, j) with i < j and Adj G i j; e_k is entry k − 1; reason: a fixed enumeration of the distinct edges
Preamble
import Definitions.Def_CallCountPOPBR_reductionInstance import Definitions.Def_CallCountPOPBR_Instance_IsValid import Definitions.Def_CallCountPOPBR_Instance_unobservedRecursive set_option autoImplicit false
Formal statement
namespace CallCountPOPBR
/-- **The reduction instance `I(G, K)`** (Section 2.1, "The reduction."). Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Section 2.1,
p.5: "Let G = (V, E) be a simple graph with V = {1, …, n} and m ≥ 1 edges, and let
1 ≤ K ≤ n − 1 … Enumerate the edges as e_1, …, e_m and let L₀ = a_z + K + m. The POPBR instance
I(G, K) has d = L₀, N = 2L₀ − 1, p = N + 1 = 2L₀, so that 2d − 1 = N, and the following
observations on the recursive indices d, …, N (the base indices 0, …, d − 1 carry no
observation): chain block … free block … target block … Here N = O(n³), so the list encoding of
Definition 2.1 has O(n³) entries, each of O(n³) bits".
There is a constant `c` such that for every simple graph `G` on `n` vertices with `m ≥ 1` edges
and every `1 ≤ K ≤ n − 1`: the edge list enumerates the edges without repetition; `I(G, K)` is a
well-formed instance with `d = L₀`, `N = 2L₀ − 1`, `p = N + 1`, `2d − 1 = N`; the base indices
are blank; the chain, free and target blocks carry exactly the printed observations and end at
`N`; exactly `K` recursive indices are unobserved; and `N ≤ c(n + 1)³` and every observed value
has at most `c(n + 1)³` bits. -/
theorem reduction_instance :
∃ c : ℕ, ∀ (G : NPGraph.Graph) (K : ℕ), NPGraph.IsSimple G → 1 ≤ numEdges G → 1 ≤ K →
K + 1 ≤ G.order →
(edgeList G).Nodup ∧
(∀ e : ℕ × ℕ, e ∈ edgeList G ↔ e.1 < e.2 ∧ NPGraph.Adj G e.1 e.2) ∧
(reductionInstance G K).IsValid ∧
(reductionInstance G K).d = L0 G K ∧
(reductionInstance G K).N = 2 * L0 G K - 1 ∧
(reductionInstance G K).p = (reductionInstance G K).N + 1 ∧
2 * (reductionInstance G K).d - 1 = (reductionInstance G K).N ∧
(∀ i, i < (reductionInstance G K).d → (reductionInstance G K).obs.getD i none = none) ∧
(∀ ℓ, 1 ≤ ℓ → ℓ ≤ zexp G.order →
(reductionInstance G K).obs.getD ((reductionInstance G K).d + ℓ - 1) none =
some (2 ^ (ℓ + 1) - 1)) ∧
(∀ k, 1 ≤ k → k ≤ K →
(reductionInstance G K).obs.getD ((reductionInstance G K).d + zexp G.order + k - 1) none =
none) ∧
(∀ k, 1 ≤ k → k ≤ numEdges G →
(reductionInstance G K).obs.getD
((reductionInstance G K).d + zexp G.order + K + k - 1) none =
some (2 * target G.order ((edgeList G).getD (k - 1) (0, 0)) - 1)) ∧
(reductionInstance G K).d + zexp G.order + K + numEdges G - 1 = (reductionInstance G K).N ∧
(reductionInstance G K).unobservedRecursive = K ∧
(reductionInstance G K).N ≤ c * (G.order + 1) ^ 3 ∧
(∀ i v, (reductionInstance G K).obs.getD i none = some v →
Nat.size v ≤ c * (G.order + 1) ^ 3) := by sorry
end CallCountPOPBR
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884dd262e4297079b8d2f7adb5deec1b329582779ed16decf34adae2411), Section 2.1, "The reduction.", p.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.