AF: Medium: New Directions in Computational Complexity

AF：中：计算复杂性的新方向

• 批准号: 0964401
• 负责人: Leslie Valiant
• 金额: $ 60万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0964401&HistoricalAwards=false
• 关键词: AF; Medium; New; Directions; Computational

Studies in computational complexity in three directions are proposed: holographic algorithms, Darwinian evolution, and multicore algorithms.In the first of these areas, holographic reductions have been shown tobe a fruitful source of new efficient algorithms for certain problems,and evidence of intractability for othrs. In this research the aim is toarrive at a better understanding of the possibilities and limitations ofholographic algorithms, by exploring ways in which specific currentlyknown limitations of this class of methods can be circumvented. Forevolution the goal is to understand better what classes of mechanismscan evolve through the Darwinian processes of variation and selectionwhen only feasible resources in terms of population sizes and numbers ofgenerations are available. In the area of multi-core algorithms, amethodology will be developed for expressing and analyzing parallelalgorithms that are optimal for a wide range of hardware performanceparameters. Such algorithms would make possible portable software, thatis aware of the parameters of the machine on which it executes, and canrun efficiently on all such machines.The work on multi-core algorithms aims to have the practical goal ofincreasing the effective exploitation of multi-core computers as thesebecome more pervasive. The work on evolution will highlight the factthat the question of how complex mechanisms could have evolved withinthe resources available, is a question that is resolvable by the methodsof computational complexity, and aims to provide more precisemathematical specifications of what the Darwinian process can achieve.The work on holographic algorithms aims to make progress in ourunderstanding of what are widely regarded as the most fundamentalquestions regarding the power of practical computation.

提出了三个方向的计算复杂性研究：全息算法、达尔文进化论和多核算法。在第一个领域，全息约简已被证明是解决某些问题的新有效算法的丰富来源，并且证明了其他问题的棘手性。本研究的目的是通过探索可以规避此类方法目前已知的特定局限性的方法，更好地理解全息算法的可能性和局限性。对于进化来说，目标是更好地理解当只有在人口规模和世代数量方面可行的资源可用时，哪些类别的机制可以通过达尔文的变异和选择过程进化。在多核算法领域，将开发一种方法来表达和分析对于各种硬件性能参数来说是最佳的并行算法。此类算法将使可移植软件成为可能，该软件了解其执行机器的参数，并且可以在所有此类机器上高效运行。多核算法的工作旨在实现提高多核的有效利用的实际目标随着计算机变得更加普及。关于进化的工作将强调这样一个事实，即复杂机制如何在可用资源内进化的问题是一个可以通过计算复杂性方法解决的问题，并且旨在为达尔文过程可以实现的目标提供更精确的数学规范。关于全息算法的研究旨在加深我们对被广泛认为是有关实际计算能力的最基本问题的理解。