Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-013 | 12th December 1994 00:00

Complexity Theory and Genetics

RSS-Feed




TR94-013
Authors: Pavel Pudlak
Publication: 12th December 1994 00:00
Downloads: 1972
Keywords: 


Abstract:

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 enviroment into genetic code. Then it can process the
information as a paralel computer. More precisely, we show that
it can simulate polynomial space computations in polynomially
many steps, even if the recombination rules are very simple.



ISSN 1433-8092 | Imprint