Two-size undecidability conjecture for partially fixed-size network coding
Two-size undecidability conjecture for partially fixed-size network coding
A partially fixed-size network has vertex set , edge set , source-message sets , demanded-message sets , and size specifications and . The specifications assign either the default size, represented by , or the fixed size to every message and edge:
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 , decide whether it is solvable. The paper has proved undecidability when additional fixed sizes and may be used; the conjecture asserts that only fixed size , together with the default size, suffices. The stated obstacle is enforcing the tristate and -state buffer conditions using only size- 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
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.