文章基本信息

标题：Decision Problems in Information Theory
本地全文：下载
作者：Mahmoud Abo Khamis ; Phokion G. Kolaitis ; Hung Q. Ngo 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：106:1-106:20
DOI：10.4230/LIPIcs.ICALP.2020.106
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Î â°â,f. Furthermore, under some restrictions, validity of conditional information constraints "with slack" is in Î£â°â,,, 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.
关键词：Information theory; decision problems; arithmetical hierarchy; entropic functions