Tag Archives: NP-complete

In Pursuit of the Traveling Salesman

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation

English: A representation of the relation amon...
English: A representation of the relation among complexity classes, which are subsets of each other. (Photo credit: Wikipedia)

This is a strange little book – and while I am happy to recommend it, I am not really clear in my own mind what sort of a book it is meant to be.

A popular description of a famous problem in the “NP” space and a gentle introduction to the whole issue of computational complexity and complexity classes? Not really, it assumes a bit too much knowledge for that.

So, a canter round the basic maths of the TSP and complexity? Not really that either, as it is light on mathematical specifics.

Still, it’s a decent book.

Why Candy Crush is so difficult – and popular?

【APP遊戲】Candy Crush Saga
Candy Crush Saga (Photo credit: Albert.hsieh)

If the evidence of my commute is any guide then Candy Crush Saga probably uses as much compute cycles as any other program in London – it is wildly popular.

And if you are player (I am not) then you shouldn’t be surprised or disappointed if you actually struggle with it – because, in fact, there are no obvious “solutions” to the “problems” you face as a player.

Toby Walsh of the University of South Wales has published a paper than shows that the “problems” of Candy Crush are in the class of what is known as “NP”.

NP problems are those which we do not know in advance what the solution is, but for which we can relatively quickly check that the solution applied is correct. In fact NP problems are at the core of internet (and most serious) encryption – internet encryption is difficult to crack in an attack but decryption is easy if the keys  are known.

NP problems are in distinction from “P” problems for which we know, in advance, both a procedure to solve the problem and to check our answer is correct. The “P” here stands for “polynomial time” – meaning we can tell how long the problem will take to solve at the start because it is some multiple (a polynomial) of its initial complexity – long division by pen and paper is a good example from everyday life – we know how to do it and we can instinctively tell how long it will take just by looking at the length of the numbers we are dividing.

Some – but not many – mathematicians believe that NP problems are really just P problems in disguise – it is just that we have not just discovered the way to solve them. In fact it can be shown that if we could find a means of solving a special class of NP problems known as “NP complete” problems then we could solve all NP problems. But most mathematicians believe that NP problems are inherently not amenable to being solved by simple procedures in polynomial time, while yet others think that such a procedure might exist but that the polynomial will be so large that we might see little advantage in cracking the problem.

In the meantime a whole industry has arisen to offer software to solve – though heuristics (informed guesses) and approximations some of the most important NP problems – such as scheduling school or train timetables.

It’s probably not an unreasonable assumption that people like Candy Crush precisely because it is so difficult and because, it would appear, no one is ever going to come up with a way of quickly solving the problems. We can get better by playing more – so that our heuristic sense of what works increases, but no one is going to emerge as an invincible player – because that is inherently not possible. Probably.

(If you want to know more and are not afraid of some maths, then P, NP, and NP-Completeness: The Basics of Computational Complexity might be worth having a look at.)

Enhanced by Zemanta

Even if P=NP we might see no benefit

A system of linear inequalities defines a poly...
A system of linear inequalities defines a polytope as a feasible region. The simplex algorithm begins at a starting vertex and moves along the edges of the polytope until it reaches the vertex of the optimum solution. (Photo credit: Wikipedia)

Inspired by an article in the New Scientist I am returning to a favourite subject – whether P = NP and what the implications would be in the (unlikely) case that this were so.

Here’s a crude but quick explanation of P and NP: P problems are those that can be solve in a known time based on a polynomial (hence P) of the problem’s complexity – ie., we know in advance how to solve the problem. NP (N standing for non-deterministic) problems are those for which we can quickly (ie in P) verify that a solution is correct but for which we don’t have an algorithmic solution to hand – in other words we have to try all the possible algorithmic solutions in the hope of hitting the right one. Reversing one-way functions (used to encrypt internet commerce) is an NP problem – hence, it is thought/hoped that internet commerce is secure. On the other hand drawing up a school timetable is also an NP problem so solving that would be a bonus. There are a set of problems, known as NP-complete, which if any one was shown to be, in reality a P problem would mean that P = NP – in other words there would be no NP problems as such (we are ignoring NP-hard problems).

If it was shown we lived in a world where P=NP then we would inhabit ‘algorithmica’ – a land where computers could solve complex problems with, it is said, relative ease.

But what if, actually, we have polynomial solutions to P class problems but there were too complex to be of much use? The New Scientist article – which examines the theoretical problems faced by users of the ‘simplex algorithm’ points to just such a case.

The simplex algorithm aims to optimise a multiple variable problem using linear programming – as in an example they suggest, how do you get bananas from 5 distribution centres with varying numbers of supplies to 200 shops with varying levels of demand – a 1000 dimensional problem.

The simplex algorithm involves seeking the optimal vertex in the geometrical representation of this problem. This was thought to be rendered as a problem in P via the ‘Hirsch conjecture‘ – that the maximum number of edges we must traverse to get between any two corners on a polyhedron is never greater than the number of faces of the polyhedron minus the number of dimensions in the problem.

While this is true in the three dimensional world a paper presented in 2010 and published last month in the Annals of MathematicsA counterexample to the Hirsch Conjecture by Francisco Santos has knocked down its universal applicability. Santos found a 43 dimensional shape with 86 faces. If the Hirsch conjecture was valid then the maximum distance between two corners would be 43 steps, but he found a pair at least 44 steps apart.

That leaves another limit – devised by Gil Kalai of the Hebrew University of Jerusalem and Daniel Kleitman of MIT, but this, says the New Scientist is “too big, in fact, to guarantee a reasonable running time for the simplex method“. Their two page paper can be read here. They suggest the diameter (maximal number of steps) is n^{log(d+2)} where n is the number of faces and d the dimensions. (The Hirsch conjecture is instead n-d .)

So for Santos’s shape we would have a maximal diameter of \approx 10488 (this is the upper limit, rather than the actual diameter). A much bigger figure even for a small dimensional problem, the paper also refers to a linear programming method that would require, in this case, a maximum of n^{4\sqrt d}\approx 10^{50} steps. Not a practical proposition if the dimension count starts to rise. (NB I am not suggesting these are the real limits for Santos’s shape, I am merely using the figures as an illustration of the many orders of magnitude difference they suggest might apply).

I think these figures suggest that proving P = NP might not be enough even if it were possible. We might have algorithms in P, but the time required would be such that quicker, if somewhat less accurate, approximations (as often used today) would still be preferred.

Caveat: Some/much of the above is outside my maths comfort zone, so if you spot an error shout it out.

An NP-complete problem from the world of embedded computing

English: Euler diagram for P, NP, NP-Complete,...
English: Euler diagram for P, NP, NP-Complete, and NP-Hard set of problems. (Photo credit: Wikipedia)

First of all – a quick explanation of P and NP. The class of problems known as ‘P’ – for polynomial (as in they can be solved in a time which is dependent on a polynomial of their complexity) – are those for which a known algorithm – a sequence of mathematical steps – to solve them exists. For instance, solving (i.e., finding the value of x where the formula evaluates to zero) x – 2 is a P class problem. NP (not P) problems are much more interesting – these are problems for which an algorithm exists but which is unknown at the time the problem is posed. In the worst case the only way of solving the problem may be to try all the potential algorithms until we find the one that solves the problem. That said, once a potential solution is found it can be verified ‘simply’ (i.e. in polynomial time). It is not known if, in fact NP problems (such as drawing up school timetables or cracking internet public key encryption) are really P type problems after all and we just have not found the solution or are permanently excluded from ‘simple’ (P) solutions. A class of NP problems called ‘NP complete‘ are those that, if shown to really be P class problems, would indicate P=NP. Most, but not all, mathematicians think, in fact P!=NP.

So, here’s the problem. It sounds simple, but as it is NP, it’s not! (I got this from Making Embedded Systems: Design Patterns for Great Software)

You have a micro controller with a timer of fixed 4MHz frequency and two 8 bit registers, a and b, such that (a) counts ticks and (b) is a match register that triggers an interrupt when the count register matches the tick count stored and a 16 bit prescaler (that allows the scaling of the ticks e.g. – if set to 2 then twice as many ticks are required to trigger the interrupt).

So how can you set the match and prescaler to work for an arbitrary frequency? Sounds like it should be easily algorithmically managed, but it’s not.

No proof of P=NP after all (yet?)

Diagram of complexity classes provided that P ...
Image via Wikipedia

Vladimir Romanov has conceded that his published “proof” of P=NP is flawed and requires further work.

So, it seems internet commerce is safe for now. But Romanov is not throwing in the towel:

Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.

A book to buy? P, NP, and NP-Completeness: The Basics of Computational Complexity – I admit to being tempted.