Undecidability of the asymptotic capacity threshold for partially fixed-size networks
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.