Definition. Polynomial time [001C]

27 April 2026

We say that the runtime of an algorithm is polynomial if its runtime is $f (n) \in O (n^{k})$ for some fixed $k$ .

Context

Note. A model of computation [001D]

27 April 2026

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.

Definition. Turing machines (informal) [0019]

27 April 2026

Arora and Barak (Complexity: § 1.1).

Let $f$ be a function that takes a string of bits…and outputs either 0 or 1. An algorrthm for computing $f$ is a set of mechanical rules, such that by following them we can compute $f (x)$ given any input $x \in [0, 1]^{*}$ . The set of rules being followed is fixed (i.e. the same rule must work for all possible input) though each rule in this set may be applied arbitrarily many times. Each rule involves one or more of the following ‘elementary’ operations:

Read a bit of the input.

Read a bit…from the scratch pad or working space we allow the algorithm to use.

Based on the values read,

Write a bit/symbol to the scratch pad.

Either stop and output 0 or 1, or choose a new rule from the set that will be applied next.

Finally, the running time is the number of these basic operations performed.

This seems quite arbitrary—

Worries about Turing machines [001B]

27 April 2026

why limit ourselves just to symbols 0 and 1?
why are the operations so limited? and
why not read multiple bits at the same time?

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.

Definition. Polynomial time [001C]

27 April 2026

We say that the runtime of an algorithm is polynomial if its runtime is $f (n) \in O (n^{k})$ for some fixed $k$ .

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.