Computational complexity of ecological and evolutionary spatial dynamics.

ABSTRACT: There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy

SUBMITTER: Ibsen-Jensen R 

PROVIDER: S-EPMC4697423 | biostudies-literature | 2015 Dec

REPOSITORIES: biostudies-literature