Collaborative Research: Studies on Average Complexity

合作研究：平均复杂度研究

• 批准号: 0429906
• 负责人: Jie Wang
• 金额: --
• 依托单位: University of Massachusetts Lowell
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2007-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0429906&HistoricalAwards=false
• 关键词: Collaborative; Research; Studies; 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.

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