Complexity theory and genetics
Pavel Pudlák · 2002
We introduce a population genetics model in which the operators are effectively computable-computable in polynomial time on probabilistic Turing machines. We shall show that in this model a population can encode easily large amount of information from environment into genetic code. Then it can process the information as a parallel computer. More precisely, we show that it can stimulate polynomial space computations in polynomially many steps, even if the recombination rules are very simple.>