AF: Medium: New Directions in Computational Complexity

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

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.