Limits on the computing power of biological systems

The theory of computational complexity and certain explicitly-stated hypotheses imply limitations on the information processing power of biological systems. Parallelism, special purpose organization, and analog mechanisms may provide speedup critical for life processes, but have little power in the face of exponential growth. We show that “polynomially simulatable” biological systems cannot exhibit dynamic behavior which produces the solution of an intractable problem. The argument implies that parallelism does not allow biological systems to defeat the exponential explosion, but rather is important because it allows polynomial time algorithms to be used more efficiently.