Measure and Information in Computational Complexity

计算复杂性的测量和信息

• 批准号: 9988483
• 负责人: Jack Lutz
• 金额: $ 24.99万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988483&HistoricalAwards=false
• 关键词: Measure; Information; Computational; Complexity

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.

主要研究者：Lutz，Jack提案编号：CCR-9988483机构：爱荷华州州立大学摘要这个项目将调查测量理论和信息理论方面的中心问题，在计算复杂性。 利用高阶复杂性理论将资源有界测度公理化，并将其推广到低复杂性（包括有限状态）类和函数类。 各种信息理论工具，包括香农熵，柯尔莫哥洛夫复杂性和实例复杂性，将研究和应用于调查平均情况下的复杂性，完整性和弱完整性，去随机化和命题证明系统的措施。 弱完备性将是一个主要的焦点，特别是与自然示例和去随机化有关。 NP不具有p测度0的假设的解释力和合理性将被进一步检验。 将调查的信息和复杂性的相关方面包括计算深度及其变体，有效的算法，成功地投注在不可预测的数据，以及在概率，随机过程和信息论的经典结果的可行effectivization。 该项目将涉及学生和其他年轻的研究人员，朝着信息理论和计算理论之间更大的综合的长期目标前进。