|
Author
|
Topic: Types of Complexity
|
Micah Sparacio
Member
Member # 6
|
posted 23. March 2003 13:18
Types of Complexity
I like gedanken's thread on irreducible complexity, especially the categorizing and defining of different versions of IC.
On that thread, we've discussed different forms of the "complexity" part of IC. In that regard, I'd like to start a thread that attempts to delineate and between different categories and sub-definitions of complexity.
Don't be afraid to include the very common types of complexity. Preferably, on the first few pages, only offer definitions without commentary.
Time Complexity - The length of time it takes to find a solution or complete a process
Space Complexity - The amount of physical storage required for a system to perform a certain operation
Kolmogorov (algorithmic) complexity - the length of the shortest program run on a universal Turing machine capable of performing a certain function or providing a certain output [ 25. March 2003, 11:44: Message edited by: Micah Sparacio ]
IP: Logged
|
|
Frances
Member
Member # 169
|
posted 23. March 2003 15:50
Complexity itself is a concept of great interest to me as it applies especially to biology. I will first provide some very useful papers which look at the issues of complexity and information and also at some of the relevant measures
I recommend the works by Chris Adami as well as Tom Schneider whose websites have excellent references to these questions.
Especially his paper What is complexity? is very helpful
What about sequence complexities such as
Kolmogorov complexity:
"This implies that a random sequence is accorded maximum Kolmogorov complexity, clearly not anything we would be interested in as biologists, because random sequences do not give rise to organisms."
Functional complexity: "McShea has also made the case for a measure of functional complexity of organisms(10) that counts the number of different functions an organism can perform."
Structural complexity:
"McShea(6) has studied several measures of structural complexity, based on number of cell types, different limb-pair types, and even the fractal dimension of sutures in ammonoids, and found some evidence for a trend in these indicators, but nothing as conclusive as one might have anticipated. "
Physical complexity:
Physical complexity(13) is a measure of sequence complexity that is carefully defined from an automata-theoretic point of view (just as Kolmogorov complexity was), but it has a very simple relationship to information theory, and turns out to be very intuitive. Furthermore, it appears to correspond exactly to what biologists think is increasing when ‘‘self-organizing systems organize themselves.’’ Because such a measure can also be applied to sequences of symbols generated by a dynamical system, there is hope that it may bridge the traditional gap between the physical and biological sciences."
Metazoan complexity and evolution: Is there a trend?
What is complexity by Christopher K. Frazier
Some Techniques for the Measurement of Complexity in Tierra
Replaying the Tape: An Investigation into the Role of Contingency in Evolution (1998)
POSSIBLE LARGEST-SCALE TRENDS IN ORGANISMAL EVOLUTION: Eight "Live Hypotheses
quote:
Historically, a great many features of organisms have been said to show a trend over the history of life, and many rationales for such trends have been proposed. Here I review eight candidates, eight "live hypotheses" that are inspiring research on largest-scale trends today: entropy, energy intensiveness, evolutionary versatility, developmental depth, structural depth, adaptedness, size, and complexity. For each, the review covers the principal arguments that have been advanced for why a trend is expected, as well as some of the empirical approaches that have been adopted. Also discussed are three conceptual matters arising in connection with trend studies: 1. Alternative bases for classifying trends: pattern versus dynamics; 2. alternative modes in which largest-scale trends have been studied: "exploratory" versus "skeptical"; and 3. evolutionary progress.
Dan McShea and the Great Chain of Being: Does Evolution Lead to More Complexity?
Other relevant links The growth of complexity
quote: blind variation and selective retention tend to produce increases in both structural and functional complexity of evolving systems
The Growth of Structural and Functional Complexity during Evolution
The minor transitions in hierarchical evolution and the question of a directional bias
quote:
The history of life shows a clear trend in hierarchical organization, revealed by the successive emergence of organisms with ever greater numbers of levels of nestedness and greater development, or `individuation', of the highest level. Various arguments have been offered which suggest that the trend is the result of a directional bias, or tendency, meaning that hierarchical increases are more probable than decreases among lineages, perhaps because hierarchical increases are favoured, on average, by natural selection. Further, what little evidence exists seems to point to a bias: some major increases are known ± including the origin of the eukaryotic cell from prokaryotic cells and of animals, fungi and land plants from solitary eukaryotic cells ± but no major decreases (except in parasitic and commensal organisms), at least at the cellular and multicellular levels. The fact of a trend, combined with the arguments and evidence, might make a bias seem beyond doubt, but here I argue that its existence is an open empirical question. Further, I show how testing is possible.
Another researcher in this area is David Waxman
Wagner comments on Waxman et al's paper "Pleiotropy and the Preservation of Perfection "
quote:
To be precise, this freezing phenomenon has been described before (9), but it was seen as an arcane result of mathematical population genetics of uncertain significance and familiar to only a very few specialists. The significance of the present report is that Waxman and Peck have shown that this obscure property of mutation-selection equations has a connection to a generic property of organisms: complexity. Each gene has many effects and functions, each character is functionally connected to multiple others. Since this is the case, the freezing of genetic and phenotypic states is a necessary outcome, just as many organismal biologists have suspected for more than a century.
This sounds great and simple, but nothing in science is ever really simple. There is always the question whether the models are producing artifacts rather than pointing to fundamental insights. There is also no definite empirical proof as to whether the Bauplan concept is a perceptual artifact or a real pattern. Both are empirical questions that need to be settled. What makes the result by Waxman and Peck nonetheless exciting is that new emergent phenomena can be discovered that are not obvious from the study of simple models. More complexity is not just more of the same, but can lead to qualitatively new phenomena. This has long been know to physicists, but there are only a handful of examples where "complexity effects" were described in population genetic models (10). These and the report by Waxman and Peck show the need to study the population genetic theory of complex adaptations as a separate problem.
Source "Complexity Matters Günter Wagner Science 279: 1158-1159 (1998)[/url] [ 23. March 2003, 16:13: Message edited by: Frances ]
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 23. March 2003 17:13
Rather than re-inventing lots of wheels, in Appendix 1 here there are brief descriptions of 47 (allegedly distinguishable) varieties of "complexity". quote: A Brief Overview of Some Existing Formulations of Complexity
This is an overview of some of the articles which directly invoke the idea of complexity in their analysis, either by defining it or by specifying its properties. There is no comprehensive overview of this subject across disciplinary borders, but there are some relevant collections:
Then follow a slew of references with, as promised, brief descriptions.
RBH [ 23. March 2003, 17:15: Message edited by: RBH ]
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 25. March 2003 11:50
RBH, My intention was not to reinvent the wheel but to collect as many different types of complexity definitions in this thread as possible. That way, it could be used as a reference spot for future discussions. Sure, most everything discussed at this board has probably been discussed in some form at another place, but there is nothing wrong with collecting information and enhancing it in some way.
Also, the principle of locality stands in my defense.
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 25. March 2003 13:37
Micah,
I understood your intention. Mine was to provide a reference to just that kind of collection already gathered in one document. I suppose to honor the 'principle of locality' I could have transcribed or C&P'ed the 47 varieties with their (paragraph or so) brief descriptions into this thread, but that seemed wasteful of bandwidth and disk space. Hence the URL reference.
RBH
IP: Logged
|
|
Micah Sparacio
Member
Member # 6
|
posted 03. April 2003 10:54
From RBH's links, I found several interesting examples that I hadn't come across before. Over the next few weeks I'm going to summarize some of these type of complexity. I'll start with the first two I happened upon:
Connectivity Complexity: The number of relations/inter-connections betwen the components of a given system. The greater the extent of inter-connections between components of a system, the more difficult it is to decompose the system without changing its behaviour.
Descriptive/Interpretative Complexity The complexity of a system which involves both a description (e.g. DNA) and a realization of the description (e.g. proteins in the cell). This complexity is measured as the total complexity of encoding the realisation into a descriptive code and decoding it back into a realisation of that code.
IP: Logged
|
|
RBH
Member
Member # 380
|
posted 13. April 2003 15:59
I'd kind of like to encourage this thread along a bit. Unfortuately, having pointed to a list of 47 conceptions of "complexity," I can't add another.
This does not introduce another concept of complexity, but is relevant to the underlying question of measuring complexity. In the most recent (May 2003) issue of Scientific American, in an article discussing the relative complexity of various versions of multiverse hypotheses/conjectures, the authors mention algorithmic information content. They write quote: But an entire ensemble is often much simpler than one of its members. This principle can be stated more formally using the notion of algorithmic information content. The algorithmic information in a number is, roughly speaking, the length of the shortest computer program that will produce that number as output. For example, consider the set of all integers. Which is simpler, the whole set or just one number? Naively, you might think that a single number is simpler, but the entire set can be generated by quite a trivial computer program, whereas a single number can be hugely long. Therefore, the whole set is actually simpler.
Similarly, the set of all solutions to Einstein's field equations is simpler than a specific solution. The former is described by a few equations, whereas the latter requires the specification of vast amounts of initial data on some hypersurface. The lesson is that complexity increases when we restrict our attention to one particular element in an ensemble, thereby losing the symmetry and simplicity that were inherent in the totality of all the elements taken together. (p. 51; emphasis added)
Here "algorithmic information" has a meaning parallel to algorithmic complexity. I'm not certain of the implications of that observation for the problem of measuring biological complexity, but I can think of at least one possibility: Is the algorithmic complexity of a biological structure appropriately measured by considering the structure in isolation, or is it more appropriate to take into account/measure some larger set of which it is a member? Is that larger set appropriately defined as currently-existing similar or related biological structures, or as all possible structures that are 'like' the target structure in some ways, or perhaps as hypothesized evolutionary precursors? I'm not sure, and I have no clear intuitions beyond it, but I have a strong feeling that it is worth thinking about. 'Context is not irrelevant' is a thought that flitted through my head when I was reading that passage the first time. What that context might be is not clear to me, though.
RBH
IP: Logged
|
|
|