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.

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