Construct · 4 fields · 7 citations
One name. Different field. Different construct. One map.
● jingle · one word, four constructs Nearest construct by meaningKolmogorov complexitycompare the meaningsEvery construct on the map is compared with every other by the meaning of its definitions, and the closest one is surfaced here. The nearest construct to complexity is Kolmogorov complexity.
Hold this as a prompt, not a verdict. Two constructs sitting close in meaning is a reason to read them side by side and decide for yourself whether they are one idea under two names. It is not proof that they are. Compare the meanings in the Collider.
Spokes are fields; dashed arcs are shared lineage. Tap a field for its definition, unit, and measures.
Drag to watch the word get claimed. Each field appears at the publication date of the earliest source cited for it. Tap a year to see which.
How the resources an algorithm consumes, chiefly running time and memory, grow as the size of its input increases. Hartmanis and Stearns fixed the modern meaning in 1965, timing Turing-machine computations and sorting problems into classes by the growth rate of the steps they demand; the term computational complexity and the field are theirs. Cook framed the central open question in 1971 by defining NP-completeness and asking whether every problem whose solution can be checked quickly (NP) can also be solved quickly (P). The referent is a problem or an algorithm, and the unit is a growth rate in the input size, written in big-O notation, not a property of any physical object or any single string. Complexity here is worst-case scaling, and it says nothing about how one particular instance happens to look.[1][2]
The length of the shortest computer program that outputs a given string and then halts, taken as the amount of information the string itself contains. Solomonoff reached the idea in 1964 through a theory of inductive inference, Kolmogorov defined it in 1965 as an absolute measure of the information in a finite object, and Chaitin arrived at it independently in 1966; the measure is now usually named for Kolmogorov. The referent is one fixed string, and the unit is the size in bits of its shortest description on a universal machine, so a random string is one that cannot be compressed and an ordered one can. This is not a growth rate over a family of inputs, as in computational complexity, and it is uncomputable in general: no algorithm returns the shortest program for every string.[3][4][5]
The behaviour that arises when many simple parts interact, so that the whole shows order, adaptation, or pattern that none of the parts holds alone. Anderson argued in 1972, under the title More is different, that at each level of scale new laws appear which cannot be read off from the level below, and that assembling many particles is a qualitative change, not just a larger sum; the argument is a founding statement of the Santa Fe tradition. The referent is a system of interacting components, a flock, a market, a brain, and complexity names its capacity for self-organised, emergent behaviour rather than any count of resources or bits. Here more parts can mean richer behaviour, the reverse of the information-theory meaning, where a longer shortest program means less structure.[6]
The structural richness of an ecological community, chiefly the number of species and the number and strength of the feeding links among them in a food web. Pimm reviewed the question in 1984, treating complexity as species richness, connectance, and interaction strength, and asked how these relate to an ecosystem's stability, overturning the earlier assumption that more complex communities are always the more stable ones. The referent is a community or food web, and the unit is a count of species and links, a property of an ecological network, not of an algorithm, a string, or an abstract system. Ecological complexity is thus measured in the field, from who eats whom, and its central debate is empirical: whether structural complexity buys stability or costs it.[7]
Next
See how complexity sits against neighbouring constructs in the Collider, or export every reference on this page in one click.
Open in ColliderExport BibTeXReport this collisionCited on this page?
If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.
Claim your construct