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’?
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.
Now available as eBook and paperback
What makes something sentient? What does it take for an entity to be aware of its own existence and to want to interact with the world of its own accord? Is it a gift from God or hard science? Is it something fundamentally human or animal in nature or is it a simple technological principle based on brain size? There are many models, of course. But, if consciousness is simply a natural product of neural complexity then eventually, in theory, we might build something – a computer or a machine – that was actually big enough to wake up!
Oh, wait …!
The widespread ramblings, which have appeared on this blog over the years, now make a partial contribution to a novel. (See http://www.lulu.com/spotlight/vicgrout)
Vic Grout’s Conscious is set a year or three into the future. The ‘Internet of Everything’ is making the world a more connected place than ever before. People’s lives are becoming increasingly automated. But something odd is happening … ‘Things’ are beginning to misbehave and no-one can work out why. What starts as an amusing inconvenience quickly becomes very serious indeed!
A ragged bunch of academics, scientists and philosophers are on the case – and may know the answer. But now they have to convince people that their crazy explanation is true. And that’s only the start. Against a backdrop of a world suddenly beginning to fall apart, they’re in a race against time to get someone to do anything about it. And not everyone is on their side!