Collaborative Research: Studies on Average Complexity

这个项目从三个方面研究了计算问题的平均复杂性。第一个方向涉及平均NP-完备性的概念，它是由Levin首先引入的，作为在平均情况分析中证明问题的难度的工具。然而，Levin最初的平均NP-完备性约简的概念似乎过于僵化，不适用于被认为是平均硬的大类问题。在该方案中，引入了一种限制较少的约简概念，并提出了一种新的工具来证明新的平均NP-Hard问题，包括分布函数求逆问题。直观地说，当且仅当随机实例的实例复杂度低时，分布问题的平均复杂度才是低的。因此，实例复杂度在平均复杂度研究中是一个有用的概念。这个项目将应用Ko等人介绍的实例复杂性的形式概念。并与Kolmogorov复杂性密切相关，研究平均复杂性。它将考察平均多项式时间可解问题、平均NP完全问题和伪随机生成器的硬实例的大小和分布。这项研究的第三个领域涉及数值计算的平均复杂性。由于数值计算的连续性，平均复杂性的概念与离散计算的概念有很大的不同。PI建议扩展Ko和Friedman提出的基于图灵机的(最坏情况)实函数复杂性理论，以发展用于数值计算的统一的平均复杂性理论。它将集中在平均复杂性和随机化之间的关系，以及基于勒贝格度量和Hausdorff维度/度量的定义在二维域上的函数的平均案例分析。平均复杂性是算法分析中的一个重要问题。实函数的平均完备性、实例复杂性和平均复杂性是计算复杂性理论和数值分析中的基本概念。这些概念之间的联系对于我们理解困难问题的平均复杂性至关重要，并有可能产生重大突破。PI是这些领域的专家。它们在基本概念的引入、平均复杂性理论和实函数复理论的发展中发挥了关键作用。平均复杂性的进步预计将对计算机科学和数学的许多领域产生重大影响，包括算法分析、数值分析、分数和混沌理论、伪随机性；并在密码学和计算机安全等更实际的领域有重要应用。PIS将把这项研究融入研究生教学。这项研究的结果将在专业会议和研讨会上广泛公布，并以调查报告和课堂讲稿的形式公布。研究生和本科生将参加这个项目的各种活动。

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.