Measure and Information in 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.