Scribd Logo
Upload

Welcome to Scribd!

  • 87 views

    Lloyd 2001 Measures of Complexity - A Nonexhaustive List

    Uploaded by

    Pedro Madeira
    The document categorizes and lists various measures that are used to quantify complexity. It groups the measures into three categories based on the questions "How hard is it to describe?", "How hard is it to create?", and "What is its degree of organization?". The first category includes information-based measures that quantify the difficulty of describing a system. The second category includes computationally based measures that quantify the difficulty of creating a system. The third category includes organizationally based measures that quantify a system's degree of structure and order. The document provides numerous examples of measures that fall into each of the three categories.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lloyd 2001 Measures of Complexity - A Nonexhaustive List

    Uploaded by

    Pedro Madeira
    87 views2 pages
    The document categorizes and lists various measures that are used to quantify complexity. It groups the measures into three categories based on the questions "How hard is it to describe?", "How hard is it to create?", and "What is its degree of organization?". The first category includes information-based measures that quantify the difficulty of describing a system. The second category includes computationally based measures that quantify the difficulty of creating a system. The third category includes organizationally based measures that quantify a system's degree of structure and order. The document provides numerous examples of measures that fall into each of the three categories.

    Original Description:

    A brief article of 2001, which lists some ways to measure the complexity of a system

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document categorizes and lists various measures that are used to quantify complexity. It groups the measures into three categories based on the questions "How hard is it to describe?", "How hard is it to create?", and "What is its degree of organization?". The first category includes information-based measures that quantify the difficulty of describing a system. The second category includes computationally based measures that quantify the difficulty of creating a system. The third category includes organizationally based measures that quantify a system's degree of structure and order. The document provides numerous examples of measures that fall into each of the three categories.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    87 views2 pages

    Lloyd 2001 Measures of Complexity - A Nonexhaustive List

    Uploaded by

    Pedro Madeira
    The document categorizes and lists various measures that are used to quantify complexity. It groups the measures into three categories based on the questions "How hard is it to describe?", "How hard is it to create?", and "What is its degree of organization?". The first category includes information-based measures that quantify the difficulty of describing a system. The second category includes computationally based measures that quantify the difficulty of creating a system. The third category includes organizationally based measures that quantify a system's degree of structure and order. The document provides numerous examples of measures that fall into each of the three categories.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    FEEDFORWARD

    Measures of Complexity: A Nonexhaustive List


    he world has grown more complex recently, and the number of ways of measuring complexity has grown even faster. This multiplication of measures has been taken by some to indicate confusion in the field of complex systems. In fact, the many measures of complexity represent variations on a few underlying themes. This column presents an (incomplete) categorization and tabulation of measures of complexity. An historical analog to the problem of measuring complexity is the problem of describing electromagnetism before Maxwells equations. In the case of electromagnetism, quantities such as electric and magnetic forces that arose in different experimental contexts were originally regarded as fundamentally different. Eventually it became clear that electricity and magnetism were in fact closely related aspects of the same fundamental quantity, the electromagnetic field. Similarly, contemporary researchers in architecture, biology, computer science, dynamical systems, engineering, finance, game theory, etc., have defined different measures of complexity for each field. Because these researchers were asking the same questions about the complexity of their different subjects of research, however, their answers have much in common. Three questions that are frequently posed when attempting to quantify the complexity of the thing (house, bacterium, problem, process, investment scheme) under study are 1) How hard is it to describe? 2) How hard is it to create? 3) What is its degree of organization? I use these questions to group measures of complexity. Measures within a group are typically closely related quantities.

    By Seth Lloyd

    Information; Entropy; Algorithmic complexity or algorithmic information content; Minimum description length; Fisher information; Renyi entropy; Code length (prefix-free, Huffman, Shannon-Fano, error-correcting, Hamming); Chernoff information; Dimension; Fractal dimension; Lempel-Ziv complexity.

    Difficulty of Creation
    Alternatively, the degree of difficulty involved in constructing or duplicating a system can form the basis of a complexity measure. Units in this case are typically those of time, energy, money, etc. Examples include: Computational complexity; Time computational complexity; Space computational complexity; Information-based complexity; Logical depth; Thermodynamic depth; Cost; Crypticity.

    Degree of Organization
    Complexity is also often related to organizational aspects. Measures in this category can be further subdivided into two subclasses. a) Difficulty of describing organizational structure, whether corporate, chemical, cellular, etc.: Effective complexity; Metric entropy; Fractal dimension; Excess entropy; Stochastic complexity; Sophistication; Effective measure complexity; True measure complexity; Topological epsilon-machine size; Conditional information; Conditional algorithmic information content; Schema length; Ideal complexity; Hierarchical complexity;
    7

    Difficulty of Description
    The complexity of a system is often associated with the degree of difficulty involved in completely describing the system. Prominent examples of these measures (typically quantified in bits) include the following:

    The author ([email protected]) is with the dArbeloff Laboratory for Information Systems and Technology, Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, U.S.A.

    August 2001

    IEEE Control Systems Magazine

    Tree subgraph diversity; Homogeneous complexity; Grammatical complexity. b) Amount of information shared between the parts of a system as the result of its organizational structure: Mutual information; Algorithmic mutual information; Channel capacity; Correlation; Stored information; Organization.

    Related Concepts
    In addition to the above measures, there are a number of related concepts that are not quantitative measures of complexity per se, but that are closely related. Such concepts include: Long-range order; Self-organization; Complex adaptive systems; Edge of chaos. I welcome additions to this list, whether or not they fall in the classification scheme adopted here.

    Product Info - www.ieee.org/magazines/DirectAccess

    IEEE Control Systems Magazine

    August 2001

    You might also like