Abstract
Underlying complexity escalates exponentially: some little-known research findings.
- Glass, R.L. Software Creativity. Prentice-Hall, 1995. See section 2.6, "Intellectual vs. Clerical Tasks," for research findings about the difficulty of solving problems in software. Google ScholarDigital Library
- Glass, R.L. Building Quality Software. Prentice-Hall, 1992. A reference to the "50 times" finding appears on page 55. Google ScholarDigital Library
- Woodfield, S.N. An experiment on unit increase in problem complexity. IEEE Transactions on Software Engineering (Mar. 1979). The source of the 25%-->100% finding.Google Scholar
Index Terms
- Sorting out software complexity
Recommendations
The VLSI Complexity of Sorting
The area-time complexity of sorting is analyzed under an updated model of VLSI computation. The new model makes a distinction between "processing" circuits and "memory" circuits; the latter are less important since they are denser and consume less ...
The Landscape of Communication Complexity Classes
We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...
Separating Complexity Classes Using Autoreducibility
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from exponential space by showing that all Turing complete sets ...
Comments