title: DNA computing, computation complexity and problem of biological evolution rate.
abstract: An analogy between the evolution of organisms and some complex computational problems (cryptosystem cracking, determination of the shortest path in a graph) is considered. It is shown that in the absence of a priori information about possible species of organisms such a problem is complex (is rated in the class NP) and cannot be solved in a polynomial number of steps. This conclusion suggests the need for re-examination of evolution mechanisms. Ideas of a deterministic approach to the evolution are discussed.
authors.affiliation: Ural State Technical University, 19 Mira St., 620002, Yekaterinburg, Russia. mav@dpt.ustu.ru
authors.forename: Alexey V
authors.initials: AV
authors.lastname: Melkikh
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology; D004247:DNA / Q000235:genetics*; D008962:Models, Theoretical; D011336:Probability
chemical_list: D004247:DNA