Computational complexity, algorithmic scope, and evolution

Biological systems are widely regarded as performing computations. It is much less clear, however, what exactly is computed and how biological computation fits within the framework of standard computer science. Here we explore the idea that evolution confines biological computation to subsets of instances that can be solved efficiently with algorithms that are ‘hardcoded’ in the system itself. We use RNA secondary structure prediction as a simple surrogate for developmental programs to demonstrate that the salient features of the genotype-phenotype map remain intact even if ‘simpler’ algorithms are employed that correctly compute the structures only for small subsets of instances, albeit quantitative differences depending on the choice of alternative algorithms can be observed.