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: this https URL DOI: https://doi.org/10.5281/zenodo.22727895%29%3B Section 8 specifies its external input and verification limits.
From: Soren Riis [view email]
[v1]
Tue, 22 Apr 2025 20:56:33 UTC (68 KB)
[v2]
Fri, 16 May 2025 11:24:49 UTC (56 KB)
[v3]
Sat, 4 Oct 2025 00:00:01 UTC (60 KB)
[v4]
Sat, 12 Sep 2026 18:05:47 UTC (18 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。