Measure and Information in Computational Complexity

项目编号：ccr -9988483单位：爱荷华州立大学摘要本项目将研究计算复杂性核心问题的测量理论和信息理论方面。资源有限测度将使用高类型复杂性理论进行公理化，并将扩展到低复杂性（包括有限状态）类和函数类。各种信息论工具，包括香农熵、Kolmogorov复杂度和实例复杂度，将被研究并与测量一起应用于研究平均情况复杂性、完备性和弱完备性、非随机化和命题证明系统。弱完备性将是一个主要的焦点，特别是在自然例子和非随机化方面。NP不具有p测度0这一假设的解释力和合理性有待进一步检验。将研究的信息和复杂性的相关方面包括计算深度及其变体，在不可预测数据上成功投注的有效算法，以及概率，随机过程和信息论中经典结果的可行有效性。该项目将包括学生和其他年轻的研究人员，他们正在朝着信息理论和计算理论之间更大的综合的长期目标前进。

PI: Lutz, JackProposal Number: CCR-9988483Institution: Iowa State UniversityAbstractThis project will investigate measure-theoretic and information-theorectic aspects of central questions in computational complexity. Resource-bounded measure will be axiomatized using higher-type complexity theory and will be extended to low-complexity (including finite-state) classes and function classes. A variety of information-theoretic tools, including Shannon entropy, Kolmogorov complexity, and instance complexity, will be studied and applied in conjunction with measure to investigation in average-case complexity, completeness and weak completeness, derandomization, and propositional proof systems. Weak completeness will be a major focus, especially in connection with natural examples and derandomization. The explanatory power and reasonableness of the hypothesis that NP does not have p-measure 0 will be further be examined. Related aspects of information and complexity that will investigated include computational depth and its variants, efficient algorithms for betting successfully on unpredictable data, and the feasible effectivization of classical results in probability, stochastic processes, and information theory. The project will involve students and other young investigators in progress toward the long-term objective of a greater synthesis between information theory and the theory of computing.