AF: Medium: New Directions in Computational Complexity

计算复杂性的研究主要集中在三个方面：全息算法、达尔文进化论和多核算法.在第一个方面，全息约简已被证明是解决某些问题的有效算法的一个富有成果的源泉，也是解决其它问题的一个棘手问题的证据.在这项研究中，目的是要达到更好地了解的可能性和局限性ofholographic算法，通过探索的方式，其中具体目前已知的限制，这类方法可以规避。进化的目标是更好地理解什么类的机制可以通过达尔文的变化和选择过程中进化时，只有可行的资源，在人口规模和数量的世代是可用的.在多核算法领域，将开发用于表达和分析并行算法的方法，这些算法对于广泛的硬件性能参数是最佳的。这样的算法将使可移植的软件成为可能，即知道它执行的机器的参数，并且可以在所有这样的机器上有效地运行。多核算法的工作旨在随着多核计算机变得越来越普遍，提高多核计算机的有效利用的实际目标。关于进化的工作将突出一个事实，即复杂机制如何在可用资源内进化的问题，是一个可以通过计算复杂性方法解决的问题，全息演算法的工作旨在使我们对被广泛认为是关于权力的最基本问题的理解取得进展。实际计算。

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.