Complexity theory and genetics
Author:
- P. PudlakPPP. Pudlak
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 383-395
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 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 simpleKeywords
This publication has 3 references indexed in Scilit:
- Mathematical Structures in Population Genetics1992
- Quadratic dynamical systems1992
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985