Collaborative Research: Studies on Average Complexity

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

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.