*OK, this blog has made some pretty wild predictions over the years; from loss of privacy & security, through societal decay from social media & 24/7 connectivity, mass unemployment by AI & automation, to industrial environmental catastrophe and a technocapitalist Armageddon. Now there’s clear evidence of the first of these forecasts coming true, any chance of taking any of the others seriously? Maybe before it’s too late might be a good idea?*

# Category Archives: Algorithms

## A ‘Reasonable Amount of Time’

*The concept of a ‘reasonable amount of time’ figures a fair bit in abstract computational complexity theory; but what is a ‘reasonable amount of time’ in practice? This post outlines the problem of balancing between the two competing ideals of determinism and adaptability and offers a flexible working definition. (Not to be taken too seriously: it’s summer vacation time.)*

A standard text on combinatorial problems and optimisation algorithms – perhaps discussing the TSP, for example – might read something like:

“… so we tend not to be as interested in particular complexity values for individual problem instances as how these complexities *change* as the input problem size (*n*) *increases*. Suppose then, that for a given problem, we can solve a problem instance of size * n = L* in a reasonable amount of time. What then happens if we increase the size of the problem from *n = L* to *n = L+1*? How much harder does the …?”

or, filling in a few gaps:

“… so we tend not to be as interested in particular complexity values for individual problem instances as how these complexities *change* as the input problem size (*n*) *increases*. Suppose then that we can solve a TSP of *20* cities on a standard desktop PC in a reasonable amount of time. What then happens if we increase the number of cities from *20* to *21*? How much longer does …?”

All good stuff, and sensible enough, but what’s this ‘reasonable amount of time’?

## Sackville Gardens

*A walk in a Manchester Park on a Sunday morning …*

Tucked away between Manchester Piccadilly and Oxford Road train stations is a quiet – but very touching – memorial to Alan Turing. In Sackville Park (or Sackville Gardens, depending on which map you consult), a figure sits, holding an apple, on a bench. Both are cast in bronze. The relief reads, ‘Alan Mathison Turing 1912-1954′ along with an ENIGMA-style coding of, ‘Founder of Computer Science’. At the figure’s feet, a further inscription reads, ‘Father of computer science, mathematician, logician, wartime codebreaker, victim of prejudice … Mathematics, rightly viewed, possesses not only truth, but supreme beauty — a beauty cold and austere, like that of sculpture’, the second part being a quotation from Bertrand Russell.