Computability of the Shannon Capacity of Finite Graphs
Determine whether an algorithm exists which, given the exact adjacency matrix of any nonempty finite simple graph G and an integer t>=1, halts and returns a rational a with |a-Theta(G)|<=2^(-t), where Theta(G)=sup_{m>=1} alpha(G^{boxtimes m})^(1/m), alpha is independence number and boxtimes is the strong graph product. No running-time bound is imposed.
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
References
Primary source
ProofAtlas open problems; Holger Boche and Christian Deppe, Computability of the Zero-Error Capacity of Noisy Channels, arXiv:2010.06873v3 (19 May 2024).
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
No solutions have been posted yet.