Complexity is a concept referring to the amount of detail required to describe a given system or result. The origin and explanation of complexity in natural, physical, and mathematical systems has been a subject of human consideration and debate for millennia and has included both theological and scientific arguments. In the modern computer age, many systems (e.g., fractals, cellular automata, and nonlinear systems involving chaos) have been discovered and devised in which a set of very simple rules leads to very complex behaviors. The investigation of such phenomena using simple programs has been undertaken by Stephen Wolfram in his ambitious work A New Kind of Science (Wolfram 2002). According to Wolfram (2002, p. 861), "Just how complexity arises was never really resolved, and in the end I believe that it is only with the ideas of this book that this can successfully be done."
Different mathematical notions make different aspects of complexity precise. For example, Kolmogorov complexity measures descriptive complexity by the length of the shortest program producing an object. By contrast, computational complexity measures the time, space, or other resources used to solve a problem relative to a specified model of computation and input size. Thus an object can have a short description while still requiring substantial resources to compute or analyze (Li and Vitányi 2008, Mitchell 2009).
