I shall take idealisation to be the ‘intentional introduction of distortion into scientific theories’ (Weisberg, ‘Idealization’: 639) (presumably with non-malicious intent). The accuracy or realism of an idealisation is not, per se, necessarily of interest. It might mislead as to the predictive inaccuracy entailed by the idealisation (Friedman, ‘Methodology’: § III.)
0.1. Example. (Acceleration in a vacuüm and in the atmosphere) In certain circumstances, we idealise the acceleration of a body on earth as if it were dropped in a vacuüm.
We could test the hypothesis by comparing the air pressure in a vacuüm and on earth. But this is ‘a foolish question by itself’. If we are dropping a ball from a building, its acceleration probably will closely approximate that in a vacuüm; but not a feather. So the putative accuracy of the antecedent idealisation is not, per se, a good guide to its legitimacy or usefulness. We should also consider the predictive inaccuracy it introduces.
Friemdan says that predictive accuracy is the ‘only relevant standard of comparison’. We need not go that far to appreciate the point that it is a relevant standard of comparison, and that the accuracy of the idealisation per se is not always relevant.
One lesson to draw from that example is that the purpose of an idealisation matters. Weisberg (‘Idealization’: § 1) distinguishes ‘Galilean’ and ‘minimalist’ idealisation. The former distorts theories to simplify them, for computational tractability—‘to get traction on the problem’ on pragmatic grounds. The latter construts and studies theoretical models containing only the ‘core causal factors which give rise to a phenomenon’. In general, idealisations’ purposes are representational ideals, e.g. (ibid.: § 2)
inclusion rules [which] tell the theorist which kinds of properties of the phenomenon [are] of interest[; and] fidelity rules [concerning] the degrees of precision and accuracy with which each part of the model is to be judged.
For instance, completeness requires inclusion of all the properties of the target phenomenon, anything external giving rise to those properties, and an analogue of any structural or causal relationship within the model, all with arbitrary accuracy and precision. Simplicity can e.g. serve pedagogical purposes, or show the minimal conditions required to generate some property. Isolating ‘only…the factors that made a difference’ can help us to formulate or analyse more complex models. Predictive accuracy may be practically useful. And so on.
Is asymptotic analysis an idealisation, and, if so, what sort of idealisation is it?
The conceptual arguments given above (Computation, cognition and language) might suggest that asymptotic analysis is not an idealisation at all. I think this is, as things go, a plausible claim. In particular, I am sceptical that the mind, in full generality, achieves some polynomial speedup relative to the standard Turing machine régime.
What about the application of the Cobham–Edmonds thesis? Even in the case of computers, it is obviously an heuristic rather than a conjecture, as I argue above. But it might be a good one.
It is a good one in computer science because it is increasingly good, because computers are always getting better. Suppose, for instance, one algorithm takes time, and another time. According to Cobham–Edmonds, the latter is tractable but the former not. This may seem silly. For instance, is merely , but is four orders of magnitude larger. It is only for larger values of that the latter becomes more efficient. In the case of hardware that is constantly becoming faster, however, we will naturally seek to solve larger problems (e.g. solve the Travelling Salesman Problem with more cities). So we will find that a considerable number of misclassifications from Cobham–Edmonds will simply turn out to be predictions that are too early. For instance, the best-known algorithm for matrix multiplication for many years was that of ?strassen1969.? It was long thought to be of only theoretical interest (Cormen et al., Introduction: 744). Now it isn’t (?huang2016.?)
Even then, the assumption is not perfect. For instance, Boolean satisfiability of 3-CNF formulæ is known to be NP-complete, by the Cook–Levin theorem (Karp, ‘Reducibility among Combinatorial Problems’ Cook, ‘Complexity’ Levin, ‘Универсальные задачи перебора’). By Cobham–Edmonds, we’d expect it to be infeasible. Yet it is feasible on sufficiently large inputs to be used in industrial applications (?marques-silva2008.?) The simplex algorithm, moreover, is asymptotically inefficient, but is preferred in practice (?spielman2003.?)
What about humans? Well, we may differ from the first humans who spoke language, but nothing like Moore’s law plausibly applies to us (?moore1965.?) There is a difference of many more orders of magnitude between computers now and those in the 1950s than those between humans now and cavemen or even many animals. It is therefore not obvious that Cobham–Edmonds can be applied to interpret the results of asymptotic analysis of language, even if the asymptotic analysis itself is sound.
We can consider, in this light, a remark of Clark and Lappin (Nativism: § 4.1).
[T]he child is, among other things, an information processing system,and is subject to the laws that govern computational systems. By studying the theoretical bounds on learning systems, we can make important inferences baout the limiting conditions of the empirical question. To take as simple analogy, the problem of determining how birds fly is an empiricla matter, but it is also clear that the principles of aerodynamics are highly relevant to this study. The bird is subject to the laws of physics, and no p lausible account will violate those laws. …[C]omplexity results…provide important insights into the intrinsic difficulty that attaches to learning particular representations.
The application of Cobham–Edmonds as a criterion of feasibility is not only to assume that on actually existing input sizes it is achievable. It is also to assume that on arbitrarily large input sizes the difficulty must not grow super-polynomially. Following the exmaple of a bird, it is a little like attempting to determine how birds might fly at arbitrarily high speeds using only polynomially more effort. It is a given that birds fly e.g. at ten miles an hour; it is not a given that the same approach will scale to e.g. Mach 3. Even a perfectly correct explanation of how a bird can fly at ten miles an hour might not scale to mach 3. If birds were able to fly at Mach 3, they would do so in accordance with the laws of computation. Similarly, if humans were to learn languages much larger than those we actually do, we plausibly would do so in accordance with the laws of computation. But neither antecedent obtains. There is no obvious a priori reason to think the methods we use in the actual world would generalise thus.
The most widely cited justification of a less critical attitude to the Cobham–Edmonds thesis is given by van Rooij (‘Tractable’){§ 2}. She argues, in effect, that Cobham–Edmonds is predictively accurate, because
increasing the speed with which a basic computational operation can be performed has very limited impact if the running time is of exponential-time complexioty…an exponential time algorithm running in time would still be impractical for all but relatively small input sizes.
This is not a wholly convincing argument. First, there are exponential functions other than ; for instance, the best known algorithm for satisfiability has complexity . This makes a difference in what is ‘relatively small’ of an order of 2.6. Second, there are some quasi-polynomial functions, that are neither polynomial nor exponential. Third, the argument seems to prove too much: it would suggest that industrial applications of SAT are impossible.
van Rooij (ibid.: § 6.9) does appear later to note the problem. She agrees that nobody would hold that
tractability is an issue if the input size is small. The problem is, of course, that for many cognitive capacities the size of the input as a whole is not small.
But she seems to think that the differences in what should count as small are themselves sufficiently small to neglect. As we have seen, this is not the case; a difference of a factor of 2.6 might be quite large—perhaps to change whether inputs of a size humans actually encounter are possible to solve.
That is, in effect, the central claim of this thesis. But it will be elaborated at various points.