This project studies the average complexity of computational problems in three directions. The first direction concerns with the notion of average NP-completeness, which was first introduced 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 rigid to be applied to a wide class of problems that are believed to be hard-on-average. In this proposal, a less restrictive notion of reductions is introduced, and is proposed as a new tool to prove 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 distributional problem 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 will apply the formal notion of instance complexity, introduced by Ko et al. and closely related to Kolmogorov complexity, to study average complexity. It will examine the size and distribu- tion of hard instances of average polynomial-time solvable problems, average NP-complete problems, and pseudorandom generators. The third area of this investigation concerns with the average complexity of numerical computation. Because of the continuous nature of numerical computation, the notion of average complexity is much different from that of discrete computation. The PIs propose to 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 numerical computation. 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 the Lebesgue 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 are fundamental concepts in computational complexity theory, as well as numerical analysis. Connections between these concepts are critical to our understanding of average complexity of 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 the fundamental concepts and the development of the average complexity theory and complexity theory of real functions. Broader Impact. Advances in average complexity are expected to have a substantial effect on many areas of computer science and mathematics, including analysis of algorithms, numerical analysis, fractals and chaos theory, and pseudorandomness; and have significant applications in more practical areas of cryptography and computer security. The PIs will integrate this research into graduate teaching. Results from this study will be presented broadly in professional conferences and workshops, and in the form of survey papers and lecture notes. Graduate and undergraduate students will participate in various activities of this project.
