Undecidability of the asymptotic capacity threshold for partially fixed-size networks

For a partially fixed-size network, let k1k_1 be the default alphabet size for default-size messages and k2k_2 the default alphabet size for default-size edges. Let k1(k2)k_1^*(k_2) be the largest possible k1k_1 for fixed k2k_2 such that the network admits a coding scheme, and define its asymptotic capacity by

lim supk2logk1(k2)logk2.\underset{k_2\to\infty}{\limsup}\frac{\log k_1^*(k_2)}{\log k_2}.

Asymptotic-capacity undecidability conjecture. The following problem is undecidable: given a partially fixed-size network (V,E,{Av},{Bv},sM,sE)(V,E,\{A_v\},\{B_v\},s_M,s_E), decide whether its asymptotic capacity is at least 11. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.