Note. A model of computation [001D]
In Asymptotic analysis of algorithms, we saw how, given a certain sort of operation on a list of numbers, we could work out how many times that operation needs to be applied to sort the list. However, in general, we should like to be able to investigate the resource-intensiveness of computations for all sort of problems. In some cases, it is not obvious what the analogous operations should be. We shall now investigate a more general approach that allows us to deal with a considerably greater number of problems. We begin with a seemingly arbitrary model of computation, and then explain why it is not so arbitrary after all.
This seems quite arbitrary—
In general, we might therefore think that the putative runtime of an algorithm required to solve a problem varies too much with respect to the model of computation. However, one class of runtimes is highly robust to such changes.
Note that this definition is relative to a model of computation. However, it turns out that the class of problems that admit polynomial-time algorithms is robust with respect to all the worries above, i.e., changing any of those features does not change the class of problems for which there are polynomial-time algorithms.
Emde Boas (Models
: § 1) puts it thus.
There exists a standard class of machine models…[that] simulate each other with polynomially bounded overhead…
This standard class corresponds, it is thought, to all ‘reasonable’ (Dean, Complexity
: § 2.2) or physically realisable models of computation. The evidence for this is in effect that no convincing counterexamples have yet been found; it is somewhat analogous, therefore, to the Church–Turing thesis.