AF: Medium: Algorithmic Complexity in Computation and Biology

Harvard University, Cambridge MA

Investigators

Abstract

Computational complexity is the field that studies how much resources are needed for performing computational tasks. Its primary focus has been to understand how many steps and how much storage space is required for performing various important tasks on conventional computers. Biological processes, can also be viewed as computations to the extent that they consist of step-by-step processes that follow certain rules, and can then be also studied from the perspective of the theory of computational complexity. This proposal is concerned with studying both of these aspects. Its goal is that of proving, by mathematical means, upper or lower bounds on the resources needed for both general purpose and evolutionary computations.   While much is understood about the complexity of computations on general purpose computers, this understanding is pivoted around a small number of critical open questions, such as the P=?NP question, the answer to which would resolve the resource requirements of numerous important tasks. The first focus of this study will be algebraic approaches to these questions, in which the limitations on computations imposed by algebraic axioms is analyzed. Holographic algorithms have over the last decade yielded novel algorithms for a variety of problems, as well as new lower bound arguments, and also new techniques for proving computational equivalence among apparently dissimilar problems. The goal of the research is to understand the inherent limits of holographic algorithms and to use this understanding to develop efficient algorithms. Darwinian evolution can be also viewed as a computational process that uses quantifiable resources, here measured in terms of numbers of generations, size of populations, and the number of experiences of individuals. Recently it was shown that the Darwinian mechanism can be viewed as a form of machine learning, the field of computer science that studies systems in which most of the information is acquired from experience and not from a programmer. The goal of the research is to understand what classes of functions, such as those occurring in protein expression networks, can so evolve using practicable resources. Graduate students will be involved in these projects.