One Unit Separates Polynomial Time from Undecidability in Term Coding
Søren Riis
math.CO
Apr 22, 2025 · v4
TL;DR
The paper's results on term-coding dispersion thresholds are machine-checked in a Lean 4.26 development of 71 modules, with axiom audits and an interactive paper.
Abstract
Term coding provides a common algebraic framework for network coding, index coding and problems in extremal combinatorics. We exhibit a decision problem in which lowering an output threshold by just one changes the complexity from polynomial time to undecidability: no algorithm then halts with the correct answer on every input. The problem concerns dispersion, the maximum number of distinct output tuples obtainable by interpreting the function symbols in a tuple of terms on a finite alphabet. We restrict inputs by inequalities between terms and ask whether a given instance meets a prescribed output threshold for some alphabet size at least two. Both thresholds are considered on the same class of instances. A machine-checked Lean development and an interactive presentation of the paper accompany this work (GitHub:
https://github.com/SR123/term-coding-disequality-lean; DOI: 10.5281/zenodo.22727895); Section 8 specifies its external input and verification limits.
Problem
Term coding gives a shared algebraic framework for network coding, index coding and extremal combinatorics. The question is how the complexity of deciding whether the dispersion of a term instance with disequality tests reaches an output threshold depends on that threshold.
Approach
Upper and lower bounds on dispersion are derived from minimum vertex cuts in the term graph, using Menger's theorem. An inequality characterization of identity functions forces group laws when the pair bound is saturated. This gives a reduction from separability of words in finite quotients of a fixed finitely presented group (Bridson–Wilton). The results are formalized in a Lean 4 development whose axiom audits use only the standard axioms, and an interactive presentation links paper claims to formal statements.
Results
Deciding whether D(n) ≥ n^k − n^{k−1} for some n ≥ 2 is undecidable. Deciding whether D(n) ≥ n^k − n^{k−1} + 1 is polynomial-time, via computation of the minimum cut ρ. Explicit cyclic-shift interpretations give dispersion n(n−1) − Mn, approaching the pair bound.