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?

By comparison, these are examples of invalid problems:

• What’s the meaning of life, the universe and everything?
• What will this week’s lottery numbers be?

This merits a little discussion before we go any further.  Problems 1-6 seem, in some sense, to be getting harder and, in fact, problem 6 might cause some distress to some.  Is this a valid problem?  What does it mean and how would we know the answer?

Well, in fact, that’s exactly the point.  Provided we can agree on what we mean by ‘best’ (shortest, quickest, cheapest, safest, etc.) and so long as we have the necessary data to work with (a list of bus, train, boat, plane fares, fuel prices, distances, trouble-spots, etc.) then it is indeed a well-defined problem and we might be able to solve it.  (Actually, that could still be beyond us; more to the point, we should be able to write a program for a computer to solve it.)  What we can’t do is solve problems we don’t understand or work without data as in the two invalid examples.

Before we move on, it’s worth noting something else.  How would you solve problem 2?  Try out every possible value for x until we find one that works?  No, of course not; that would take a ridiculously long time, arguably an infinitely long time (which would be awkward, even for a computer).  We’d just do a little bit of algebra – some rearranging – and it’s only a few steps.  Well, OK, that’s pretty obvious but we’ve already seen a more convincing example of good and bad problem-solving.  There’s an early point to note here: we can’t just decide how hard a problem is on the basis of any old method (algorithm) we might use on it.  The algorithm may be making the problem look harder than it is.  But this throws up a very thorny question: how do we know we’ve got the best algorithm for a problem?  Well, in general terms, we often don’t.

Let’s take a more interesting, actually a quite famous, example …  The Travelling Salesman Problem (TSP) (yes, nowadays it should probably be the Travelling Salesperson Problem or something more politically correct but it just isn’t) models an itinerant pedlar moving from place to place, trying to sell their wares.  In general terms they have to visit a number (usually ‘n‘) cities in some order, typically returning to where they started from.  Assuming we can agree what we mean by ‘best’ in any given context (distance, cost, time, etc.), what’s the best order in which to visit the cities?  Easy enough?  Well, just consider how big the problem might be before we go any further.

OK, let’s start by considering how many possible solutions there are.  We’re looking for the best ordering on n cities.  How many choices for the first city?  That’s n.  How many for the second (having already chosen the first).  That’s n-1.  n-2 for the third and so on … When there are only two left, there are 2 choices for the second-to-last then only 1 for the last.  So the total number of different solutions is n x n-1 x n-2 x … x 2 x 1, which we call n factorial and write as n! for short.

Factorials get very big, very quickly.  (Suppose 1! = 1 is 1 metre away.  2! = 2 is two metres away.  6! = 720 is 720 metres away, maybe at the end of the street?  Where are you at 12! ?)  But computers are good at dealing with large numbers so is this really a problem?  Well, in absolute terms (i.e. for a given value of n), it rather depends, but what definitely is difficult is the way these numbers grow as n grows.

Imagine we have a machine that can just about deal with a TSP of (oh, say) 20 cities.  What that means (for now) is that it can examine the 20 x 19 x 18 x … x 2 x 1 = 20! possible solutions (forget the actual value of 20!; it doesn’t really matter) in a reasonable amount of time.  A ‘reasonable amount’ of time, in turn, depends on the circumstances.  (If you’re planning a Mars mission in five years’ time, you might have five years on a powerful computer; if you’re processing packets on an Internet router, you might only have a fraction of a second on a low-end processor.)  Again, it doesn’t really matter; it’s a reference point, no more.  A more relevant issue is what’s then involved in solving a TSP with one extra city?

Well, that’s 21! of course, which is 21 x 20!; in other words, 21 times as many possible solutions to search through.  If we’re on the cutting edge of existing technology for 20 cities, then, even if Moore’s Law keeps going, it’s going to take a few years before we have a processor that’s up to it.  That’s years just for that one extra city.  Increasing to 30 cities, we’ll have to wait several decades for a suitable machine.  What we’ve got now won’t save us; nor will our current rate of advance.

In fact, we can get quite fanciful about this …  Let’s build the perfect computer …  Suppose we turn the Universe into a computer and run it as efficiently as theoretically possible.  Suppose every sub-atomic particle in the Universe is a component of the computer.  Suppose we manage to perform a calculation every time a sub-atomic particle anywhere in the universe changes quantum state, for as many such particles as there are, for as many states as they can have, as often as such changes are possible and we run the whole thing for the lifetime of the Universe.  (OK, we might be a bit hazy on the actual implementation details for this perfect computer but it’s just an exercise.)  What’s the biggest TSP we can solve?

Amazingly, particularly in the context of problems like the TSP, that’s not such an impossible question to answer.  Opinions will differ on some of the parameters (number of particles, lifetime of the universe, etc.) but the complexity of the TSP increases so quickly (it increases exponentially quickly) that a few orders of magnitude (powers of ten) here or there really don’t make that much difference.  However you estimate these values, it turns out that the entire universe, acting as a perfect computer, probably can’t solve a TSP (by looking at all the possible solutions) for 100 cities.  That’s an astonishing result; it means that a TSP of, say, 120 cities, whilst theoretically calculable, is as effectively unsolvable as the Halting Problem.

(A quick aside could be a good idea here.  It might sound like we’re getting close to talking about quantum computing.  We’re not really, although that might eventually have some relevance to these really big problems.  We’ll have to leave that for a separate post.)

OK, there’s a huge assumption here of course.  We’re working on the basis that the best or only way (algorithm) to solve a TSP is to try out all the possible routes, one at a time, to see which is best, and that might be as silly as it was for problem 2 at the start of this piece.  If there’s a better way, it might not take anything like as long.  Well, here’s the thing … no-one knows of an algorithm that’s very much better than the exhaustive search method we’ve been describing.  (There are alternatives that bring the run time complexity down a bit, but not much, and generally at the expense of eating up huge amounts of memory space as they run.  There are also a variety of approaches that exploit particular features of particular cases, but we’re talking in general terms here.)  So does that mean that there’s no alternative method that’s (significantly) better?  No, it just means we haven’t found one.  By the same token, no-one’s ever proved that no such improved algorithm exists.  So, where does that leave us?

Well, in simple terms, it means we don’t currently know how to solve big, general instances of some types of problem.  More generally, we don’t know if we ever will.  We need one of two things to resolve this: either an improved algorithm that ‘cracks’ the problem or a mathematical proof that no such algorithm can exist.  Either’s conceivable and things have fallen out both ways in the past (although most mathematicians and computer scientists suspect the latter).  But, at the heart of this little puzzle is a much deeper mystery because the TSP isn’t alone; there are a lot of other problems very, very like it.

This (above) is what the situation might look like.  Within the set of all problems, including the entirely unsolvable ones, lies a set of, for want of a better word, reasonable ones.  These problems, grouped together under the heading ‘NP’ for historical reasons (we’ve kind of changed the definition since they were originally named although the result’s still the same) are any problems that, although it might be difficult to find a good solution, it’s easy enough to check a potential solution if someone hands it to us.  Within NP, we know there are some easy problems, 1-6 above for example (which we call ‘P’).  Then it seems, there’s another, non-intersecting set, which contains the TSP and its cousins, which we call ‘NP-complete’.  (If you’re interested in what these letters actually mean, see here – as well as a more sophisticated version of that diagram and a few other ideas.)  The problems in NP-complete are equivalent in the sense that:

1. If we could find a simple algorithm for any one of them, it could be easily adapted to work for all of the rest
2. If we could prove that no easy algorithm exists for any one of them, then this proof could be tweaked to prove the same for all of them

In other words, resolving the easy/hard question for any of the NP-complete problems would resolve it for all of them.  If the problems in NP-complete really are hard (that is, if it’s not just collectively poor algorithmic design on behalf of the human race) then NP-complete is a distinct set from P.  Or, even simpler, there are some NP problems that are not in P.  P ≠ NP.  If, on the other hand (and this would be a big surprise), someone finds an easy solution to an NP-complete problem, then all the NP-complete problems slide into P and P expands to become NP. P = NP.

So the situation, at the moment is that we may know if a problem’s easy; otherwise we’re not sure.  To list a few simple, but unsettlingly diverse,  examples:

• The ‘Shortest Path Problem‘, problem 6 above (finding the shortest route from one point to another) is EASY
• The ‘Shortest Tour Problem’, the TSP (finding the shortest way of visiting a number of points and returning to the start) appears to be HARD
• The ‘Minimum Spanning Tree Problem‘ (finding the least wire required to connect a wired network) is EASY
• The ‘Minimum Connected Dominating Set Problem‘ (finding the fewest relay switches to connect a wireless network) appears to be HARD

So, all in all, it’s pretty difficult to spot a pattern and the essential question remains unanswered.  Is P = NP?.  Apart from anything else, there’s a lot of money riding on it and it’s attracting the attention of the great minds of our time …

That’s a real snap from the Simpsons by the way; Homer’s brief dalliance with the world of mathematics.  What’s interesting is that most of the equations and suchlike that float around Homer in this episode are known to be true.  (The thing on the right, for example, is one of the most remarkable equations in mathematics.  If you add 1 to both sides, it ties together the five key values known to mathematicians.)  P = NP stands out as being something we don’t think is true.  As MIT’s Scott Aaronson puts it,

“If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…”

Despite all the expert opinion to the contrary, does Homer know something we don’t?