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 to be a fruitful source of new efficient algorithms for certain problems, and evidence of intractability for othrs. In this research the aim is to arrive at a better understanding of the possibilities and limitations of holographic algorithms, by exploring ways in which specific currently known limitations of this class of methods can be circumvented. For evolution the goal is to understand better what classes of mechanisms can evolve through the Darwinian processes of variation and selection when only feasible resources in terms of population sizes and numbers of generations are available. In the area of multi-core algorithms, a methodology will be developed for expressing and analyzing parallel algorithms that are optimal for a wide range of hardware performance parameters. Such algorithms would make possible portable software, that is aware of the parameters of the machine on which it executes, and can run efficiently on all such machines.
The work on multi-core algorithms aims to have the practical goal of increasing the effective exploitation of multi-core computers as these become more pervasive. The work on evolution will highlight the fact that the question of how complex mechanisms could have evolved within the resources available, is a question that is resolvable by the methods of computational complexity, and aims to provide more precise mathematical specifications of what the Darwinian process can achieve. The work on holographic algorithms aims to make progress in our understanding of what are widely regarded as the most fundamental questions regarding the power of practical computation.
