Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

complexity theory




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