 # Tag Archives: Computational complexity

## 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’?

## Are There Any Hard Problems?

That looks like a hopelessly vague question, and it is unless we’re prepared to clarify it a bit.  On the other hand, we already know there are some impossible problems so surely there are some that are just hard?  Again, we’ll need to work out what on earth we’re talking about here.  Let’s start with what we actually mean by a problem in a computational sense …

(Be warned: There are one or two simplifications and liberties with precision in what follows; it’s well-intentioned but may upset the purist.)

Well, actually, even that isn’t simple and there’s no absolute agreement on what a good definition would be.  (We’ve seen previously that mathematicians and computer scientists don’t always see eye-to-eye.)  It’s cheating a bit but it’s probably easier to give examples and this should work well enough for us.  At least in the context of computing, these are all valid problems:

1. Calculate    2 x 4 + 9 – 3
2. If   5 – x  =  2   what’s x?
3. Find the largest from    5, 7, 1, 4, 8, 5, 2, 4, 8, 5, 2, 6, 7, 7, 3, 3, 2, 4, 3, 6, 7, 7, 6, 5, 4
4. Sort    25, 44, 66, 72, 12, 45, 56, 90, 45, 69, 11, 10, 12, 42, 88     into ascending order
5. Arrange   1, 2, 3, 4, 5, 6, 7, 8, 9   into a magic square
6. What’s the best way to get to Paris?