A part of the theory of computation that has to with the resources needed to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.
Related category CHAOS, COMPLEXITY, AND DYNAMICAL SYSTEMS
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact