Undecidability of the asymptotic capacity threshold for partially fixed-size networks
Undecidability of the asymptotic capacity threshold for partially fixed-size networks
For a partially fixed-size network, let be the default alphabet size for default-size messages and the default alphabet size for default-size edges. Let be the largest possible for fixed such that the network admits a coding scheme, and define its asymptotic capacity by
Asymptotic-capacity undecidability conjecture. The following problem is undecidable: given a partially fixed-size network , decide whether its asymptotic capacity is at least . This is proposed as a future direction; the source gives no resolution or supporting reduction beyond stating the conjecture.
Sources & referencesView supporting material
Primary source
Cheuk Ting Li, “The Undecidability of Network Coding with some Fixed-Size Messages and Edges”, arXiv:2109.08991 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.