Complexity


Complexity

 

    • The term complexity has many different meanings. At least
      one adjective is needed to help distinguish between different uses of the word.
  • Increasing Complexity
    • This paper describes and classifies several measures and models of compexity, recounts previous attempts at increasing complexity in artificial ecologies, and offers some suggestions for future studies into artificial complexity.

 

 

Structural Complexity
 

    • Abstract: attempt to understand and to measure the notion of complex structure in networks.
    • Authors: Anastasiadis, Costa, Gonzales, Honey, Szeliga, Terhesiu.
    • 2005
    • Abstract: In this paper, an objetive and quantitative methodology for developing a stand scales index of structural complexity is demosnstrate.
    • Authors: McElhinny , Gibbons, Brack.
    • 2006
    • Abstract: A new complexity measure for graphs and networks is proposed. The central idea of OdC is to apply an entropy measure to the degree correlation matrix, after summation over the offdiagonals. This allows for a quantitative,yet still approximative, measure of complexity. OdC roughly is ‘hierarchysensitive’ and has the main advantage of being computationally not costly.
    • Abstract: The present paper tries to clarify the growth of complexity during evolution by analysing the concept of
      complexity as a combination of variety and dependency.
    • Author: Heylighen .
    • 1999
    • Abstract: To analyze the evolutionary emergence of structural complexity in physical processes we introduce
      a general, but tractable, model of objects that interact to produce new objects. Since the objects have well defined structural properties, we demonstrate that complexity in the resulting population dynamical system emerges on several distinct organizational scales during evolution sustaining interaction.
    • Authors: Crutchfield , Gornerup .
    • 2004
    • Abstract: Computational mechanics, an approach to structural complexity, defines a process's causal states and gives a procedurefor finding them. They show that the causal-staterepresentation|an Epsilon-machine|is the minimal one consistentwith accurate prediction.
    • Authors: Shalizi, Crutchfield
    • 2001
  • When Evolution is Revolution. Origins of Innovation
    • Abstract: A pictorial tour of the theories of epochal evolution and structural complexity is presented with a view toward the dynamical origins,stabilization, and content of evolutionary innovations.
    • Author: Crutchfield
    • 2001
    • Abstract:we propose to use the average atom density (AAD) and the average atom scale (AAS) to evaluate the structural complexity of neural signals.
    • Authors: Tong, Thakor, Hopkins
    • 2005
  • Measuring structural complexity for Class Diagrams: An Information Theory Approach
    • Abstract: this paper presents a structural complexity model called weightedclass dependence graph (WCDG).
    • Authors: Zhou, Xu
    • 2005
    • Abstract: We show that the rate of increase in thermodynamic depth, or dive, is the system’s reverse-time Shannon entropy rate, and so depth only measures degrees of macroscopic randomness,not structure. To fix this, we redefine the depth in terms of the causal state representation—e-machines—and show that this representation gives the minimum dive consistent with accurate prediction.
    • Authors: Crutchfield, Shalizi
    • 1999
    • Abstract: The central thesis of this work is that concepts, techniques, and ideas related to pseudorandomness and quasirandomness should find significant applications in the field of structural complexity theory.
    • Author: Sivakumar
    • 1996
  • On the Structure of Valiant’s Complexity Classes
    • Abstract: Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. They further develop this theory in the spirit of structural complexity and obtain analogues ofwell-known results by Baker, Gill, and Solovay, Ladner, and Schöning.
    • Author: Bürgisser
    • 1999
    • Abstract: They introduce a technique of aritmetization of the process of computation in order to obtain novel characterizations of certain complexity classes via multivariate polynomials.
    • Authors: Babai, Fortnow.
    • 1991
    • Abstract:
    • Authors: McCabe
    • 1976
    • Abstract:present a complexity measure for studying
      the structural complexity of multi-agent robot formations.
    • Authors: Muhammad, Egerstedt
    • Abstract: propose a measure of structural complexity for binary strings based on the amount of change incorporated in a string.
    • Authors: Aksentijevic, Gibson
    • 2003
    • Abstract: studied complexity of the stock market by modeling epsilon-machine of Standardand Poor’s 500 index from February 1983 to April 2006 using causal-state splittingreconstruction algorithm.
    • Authors: Park, Won Lee, Yang, Jo, Moon.

 

Links

  • Structural Complexity Laboratory
    • The Structural Complexity Laboratory aims to develop, extend and apply automated methods for dealing with problems whose complexity is unknown.
    • This site constains proposed contributions to a Special Issue of the Journal COMPLEXITY in which researchers across the sciences are invited to reflect on the role of nerworks and nerwork dynamics in their primary research areas.
    • 2002

 

Complexity of sequences:

  • Deterministic Complexity and Entropy
    • Abstract: Lempel and Ziv (1976) proposed a computable string production-complexity. In this
      paper, their emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. The linearized measure enables them to propose an entropy measure, observed elsewhere to correspond closely with the Kolmogorov-Sinai entropy in simpledynamical systems.
    • Authors: Titchener, Nicolescu, Staiger, Gulliver, Speidel.
    • 2005
    • Abstract: A new approach to the problem of evaluatinf the complexity of finite sequences is presented. the proposed complexity measure is related to the numver of steps in a self-delimitinf production process by which a given sequence is presumed to be generated.
    • Authors: Lempel, Zip
    • 1976
    • Abstract: They use to measure the complexity of finite strings, in terms of the number of steps required to recursively constructthe string from its alphabet.
    • Author: Titchener
    • 2000
    • Abstract: We provide a proof that the expected length of the shortest feedback register to generate a sequence of length n is less than 2 log p n+ o(1), and also give several other statistics of interest for distinguishing random strings.
    • Authors: O'Connor, Snider.


Graph theory

 

    • Abstract: An operation of concatenation is introduced for graphs.
    • Abstract: consider an algorithm that for each connected graph yields an irreducible subgraph.
    • Authors: Koyama, Neel , Orrison.
    • submitted.

 

Graph complexity


The complexity of a graph has been measured in several different ways:

  • The number of boolean operations, based on a pre-determined set of bolean operators (usually union and interseccion) necessary set  of graphs:  
  • The linear complexity of any one of the graph's adjacency matrixs:

  • The number of its spanning trees:
  •  Graph complexity and the Laplacian matrix in blocked experiments, Linear and Multilinear Álgebra.
  • Parametrer for the complexity of finite directed graphs which measures to what extent the cycles of the graph are intertwined:

 

Graph rewriting

 

Fitness Landscapes

    • Abstract: cast come classes of fitness landscapes as problems in spectral analysis on various Cayley graphs.
    • Authors:Rockmore , Stadler , Kostelec , Hordijk
    • 2002
    • Abstract: connections of landscape theory with algebraic combinatorics and random graph theory.
    • Authors: Reidys, Stadler
    • 2002
    • Abstract: procedure for estimating the amplitude spectra based on certain correlation functions that are easily obtained from empirical studies of the landscapes.
    • Authors: Hordijk, Stadler
    • 1998
    •  Abstract: apply random graph theory to perform the mapping of RNA-molecules to secondary structures which is a good example to study principles of evolucionary optimization.
    • Authors: Kopp, Reidys, Schuster .
    • 1996
    • Abstract: techniques based on evolvability statistics of the fitness landscape surrounding sampled solutions.
    • Abstract: method for approximating a fitness landscape as a superposition of “elementary” landscapes.
    • Authors: Happel, Stadler
    • 1996
    • Abstract: The Travelling Salesman Problem and NKp Fitness Landscapes.

 

Evolution

    • Author: Wright
    • 1889
    • Abstract: htmlified version of Charles Darwin's "The Origin of Species"
    • 1859

 

Links

    • People, research, writings.
    • Conferences, journals.

 

  • GRACO 2005
    • Is an international forum for researchers in all areas of combinatorics, graphs and algorithms.

 

    • is a collection of links to home pages of graph theorists.


    • The Structural Complexity Laboratory aims to develop, extend and apply automated methods for dealing with problems whose complexity is unknown


    • why do we study the complexity of the evolution?
    • In Spanish