Collaborative Research: Studies on Average Complexity

点击翻译按钮获取中文摘要

AbtractThis project studies the average complexity of computational problems in three directions.The first direction concerns with the notion of average NP-completeness, which was firstintroduced by Levin as a tool to prove the hardness of a problem in average-case analysis.Levin's original notion of reductions for average NP-completeness, however, seems too rigidto be applied to a wide class of problems that are believed to be hard-on-average. In thisproposal, a less restrictive notion of reductions is introduced, and is proposed as a new tool toprove new average NP-hard problems, including distributional function inverting problems.The second direction of this project investigates the relations between instance com-plexity and average time-complexity. Intuitively, the average complexity of a distributionalproblem is low if and only if the instance complexity of a random instance is low. Thus,instance complexity is a useful concept in the study of average complexity. This project willapply the formal notion of instance complexity, introduced by Ko et al. and closely related toKolmogorov complexity, to study average complexity. It will examine the size and distribu-tion of hard instances of average polynomial-time solvable problems, average NP-completeproblems, and pseudorandom generators.The third area of this investigation concerns with the average complexity of numericalcomputation. Because of the continuous nature of numerical computation, the notion ofaverage complexity is much different from that of discrete computation. The PIs proposeto extend the Turing machine-based (worst-case) complexity theory of real functions, intro-duced by Ko and Friedman, to develop a unified average complexity theory for numericalcomputation. It will focus on the relations between average complexity and randomization,and the average-case analysis of functions defined on two-dimensional domains, based on theLebesgue measure and the Hausdorff dimension/measure.Intellectual Merit. Average complexity is an important issue in analysis of algorithms.Average completeness, instance complexity, and average complexity of real functions arefundamental concepts in computational complexity theory, as well as numerical analysis.Connections between these concepts are critical to our understanding of average complexityof hard problems, and have potential to generate major breakthrough.The PIs are experts in these areas. They have played key roles in the introduction of thefundamental concepts and the development of the average complexity theory and complexitytheory of real functions.Broader Impact. Advances in average complexity are expected to have a substantialeffect on many areas of computer science and mathematics, including analysis of algorithms,numerical analysis, fractals and chaos theory, and pseudorandomness; and have significantapplications in more practical areas of cryptography and computer security.The PIs will integrate this research into graduate teaching. Results from this study willbe presented broadly in professional conferences and workshops, and in the form of surveypapers and lecture notes. Graduate and undergraduate students will participate in variousactivities of this project.