Two-size undecidability conjecture for partially fixed-size network coding

A partially fixed-size network has vertex set VV, edge set EE, source-message sets Av\\{A_v\\}, demanded-message sets Bv\\{B_v\\}, and size specifications sMs_M and sEs_E. The specifications assign either the default size, represented by 00, or the fixed size 22 to every message and edge:

sM(i),sE(u,v){0,2}for all i,u,v.s_M(i),s_E(u,v)\in\{0,2\}\quad\text{for all }i,u,v.

A network is solvable if there exist encoding and decoding functions satisfying all demands. Two-size undecidability conjecture. The following decision problem is undecidable: given such a partially fixed-size network (V,E,{Av},{Bv},sM,sE)(V,E,\{A_v\},\{B_v\},s_M,s_E), decide whether it is solvable. The paper has proved undecidability when additional fixed sizes 33 and 55 may be used; the conjecture asserts that only fixed size 22, together with the default size, suffices. The stated obstacle is enforcing the tristate and (4+1)(4+1)-state buffer conditions using only size-22 edges.

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.