论文标题
信息理论中的决策问题
Decision Problems in Information Theory
论文作者
论文摘要
熵的约束被认为是信息理论定律。尽管对他们的发现的追求一直是信息理论研究的核心主题，但在熵上的约束算法方面仍未得到探索。在这里，我们通过将几个不同的此类问题置于算术层次结构的水平，对熵的决策问题进行调查。我们在检查所有几乎纳入功能的有效性时建立了以下结果：首先，由单调布尔公式产生的布尔信息约束的有效性是共同追求的；其次，“紧密”条件信息约束的有效性为$π^0_3 $。此外，在某些限制下，条件信息约束“带有松弛”的有效性为$σ^0_2 $，信息不平等约束的有效性涉及最大值等同于信息不平等约束的有效性（不涉及最大值）。我们还证明，有条件独立性陈述的经典含义问题是共同选举的。
Constraints on entropies are considered to be the laws of information theory. Even though the pursuit of their discovery has been a central theme of research in information theory, the algorithmic aspects of constraints on entropies remain largely unexplored. Here, we initiate an investigation of decision problems about constraints on entropies by placing several different such problems into levels of the arithmetical hierarchy. We establish the following results on checking the validity over all almost-entropic functions: first, validity of a Boolean information constraint arising from a monotone Boolean formula is co-recursively enumerable; second, validity of "tight" conditional information constraints is in $Π^0_3$. Furthermore, under some restrictions, validity of conditional information constraints "with slack" is in $Σ^0_2$, and validity of information inequality constraints involving max is Turing equivalent to validity of information inequality constraints (with no max involved). We also prove that the classical implication problem for conditional independence statements is co-recursively enumerable.
