论文标题
网络编码，有条件信息不平等和有条件独立性的不可证实性
Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication
论文作者
论文摘要
我们解决了三个长期的开放问题，即网络编码的（算法）可决定性，条件信息不平等的可决定性以及随机变量之间有条件独立性暗示的可决定性，通过表明这些问题是不可避免的。该证明利用了赫尔曼（Herrmann）对嵌入式多价数据库依赖的论点的启发，该依赖性是由Dougherty，Freinger和Zeger研究的网络，以及一个新颖的结构，以代表网络顶部的群体自动形态。
We resolve three long-standing open problems, namely the (algorithmic) decidability of network coding, the decidability of conditional information inequalities, and the decidability of conditional independence implication among random variables, by showing that these problems are undecidable. The proof utilizes a construction inspired by Herrmann's arguments on embedded multivalued database dependencies, a network studied by Dougherty, Freiling and Zeger, together with a novel construction to represent group automorphisms on top of the network.
