Essential complexity
Encyclopedia
Essential complexity refers to a situation where all reasonable solutions to a problem must be complicated (and possibly confusing) because the "simple" solutions would not adequately solve the problem. It stands in contrast to accidental complexity
, which arises purely from mismatches in the particular choice of tools and methods applied in the solution.
This term has been used since, at least, the mid-1980s. Turing Award
winner Fred Brooks
has used this term and its antonym of accidental complexity
since the mid-1980s. He has also updated his views in 1995 for an anniversary edition of Mythical Man-Month, chapter 17 "'No Silver Bullet' Refired".
. In this context, essential complexity refers to the cyclomatic complexity after iteratively replacing all well structured control structures with a single statement. Structures such as if-then-else and while loops are considered well structured. Unconstrained use of goto statements can produce programs which can not be reduced in this way.
For example, the following C program fragment has an essential complexity of 1, because the inner if statement and the for can be reduced:
for(i=0;i<3;i++) {
if(a[i] 0) b[i] += 2;
}
The following C program fragment has an essential complexity of more than one. It finds the first row of z which is all zero and puts that index in i; if there is none, it puts -1 in i.
for(i=0;i
}
goto found;
}
non_zero:
i = -1;
found:
See also
Accidental complexity
Accidental complexity is complexity that arises in computer programs or their development process which is non-essential to the problem to be solved...
, which arises purely from mismatches in the particular choice of tools and methods applied in the solution.
This term has been used since, at least, the mid-1980s. Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
winner Fred Brooks
Fred Brooks
Frederick Phillips Brooks, Jr. is a software engineer and computer scientist, best known for managing the development of IBM's System/360 family of computers and the OS/360 software support package, then later writing candidly about the process in his seminal book The Mythical Man-Month...
has used this term and its antonym of accidental complexity
Accidental complexity
Accidental complexity is complexity that arises in computer programs or their development process which is non-essential to the problem to be solved...
since the mid-1980s. He has also updated his views in 1995 for an anniversary edition of Mythical Man-Month, chapter 17 "'No Silver Bullet' Refired".
Cyclomatic complexity
Essential complexity is also used with a different meaning in connection with cyclomatic complexityCyclomatic complexity
Cyclomatic complexity is a software metric . It was developed by Thomas J. McCabe, Sr. in 1976 and is used to indicate the complexity of a program. It directly measures the number of linearly independent paths through a program's source code...
. In this context, essential complexity refers to the cyclomatic complexity after iteratively replacing all well structured control structures with a single statement. Structures such as if-then-else and while loops are considered well structured. Unconstrained use of goto statements can produce programs which can not be reduced in this way.
For example, the following C program fragment has an essential complexity of 1, because the inner if statement and the for can be reduced:
for(i=0;i<3;i++) {
if(a[i] 0) b[i] += 2;
}
The following C program fragment has an essential complexity of more than one. It finds the first row of z which is all zero and puts that index in i; if there is none, it puts -1 in i.
for(i=0;i
}
goto found;
}
non_zero:
i = -1;
found:
See also
- History of software engineeringHistory of software engineeringFrom its beginnings in the 1940s, writing software has evolved into a profession concerned with how best to maximize the quality of software and of how to create it...
- Software prototypingSoftware prototyping*Software prototyping, refers to the activity of creating prototypes of software applications, i.e., incomplete versions of the software program being developed...
(one of the main strategies against essential complexity in "No Silver Bullet") - Decision-to-decision pathDecision-to-decision pathA decision-to-decision path, or DD-Path, is a path of execution that does not include any conditional nodes...
- Occam's RazorOccam's razorOccam's razor, also known as Ockham's razor, and sometimes expressed in Latin as lex parsimoniae , is a principle that generally recommends from among competing hypotheses selecting the one that makes the fewest new assumptions.-Overview:The principle is often summarized as "simpler explanations...
- No silver bulletNo Silver Bullet"No Silver Bullet — Essence and Accidents of Software Engineering" is a widely discussed paper on software engineering written by Fred Brooks in 1986...
- Cyclomatic complexityCyclomatic complexityCyclomatic complexity is a software metric . It was developed by Thomas J. McCabe, Sr. in 1976 and is used to indicate the complexity of a program. It directly measures the number of linearly independent paths through a program's source code...