P vs NP problems – progress?

The problem of commputability has been with computer scientists and other types for some time.

Norbert Blum, a distinguished mathematician, appears to have made progress on the problem.  I am not a computer scientist, but John Baez (mathematical physicist) has a good blog on the subject here -> Norbert Blum on P versus NP.

I add some fairy-wheels here.

The author has published a preprint – that means that experts still need to referee the paper, but the author has made it available to the rest of us in the meantime. A lot of preprints are published that do not pass muster. Nevertheless this paper seems to have cleared the initial BS filters.

What he has done, in best mathematical tradition, is partition the set of possible problems as being NP-Hard, HP-Complete, NP and P (Left Hand Side) and not just the two alternatives of the Right Hand Side.

 

So what problems are we talking about and what does P and N mean?

First, problems of type NP are computational problems can be solved in nondeterministic polynomial time – that means there is some number α, such that solving a problem takes less than tα where “t” is time.

Thus a problem that can be solved in time t is better than a problem that can be solved in time t2. The next step is to understand that any problem that can be solved in time tn is much quicker than et.

(Yes you can add some scalar factor like 0.00001 to damp the exponential time. But for t large enough, the wookie always gets you.)

NP-complete problems are the set of problems whose solutions can be verified in polynomial time.

At a conference in 1971  the question of whether all NP-complete problems were solvable in polynomial time was framed. This question is represented as P=NP, that is, is whether the set of problems that can be verified in polynomial time are also solvable in polynomial time.

This is now one of the great unsolved problems of mathematics and profoundly affects algorithm design in computation.

So what kind of problems? For example, the travelling salesman problem: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” This is for example useful in the airline industry. Another example is the graph colouring problem, which asks whether there is a way of colouring the vertices of a graph so that that no two adjacent vertices share the same colour, for a certain minimal number of colours.

Solving these problems is easy on a case by case basis – the problem is finding a general solution.

Back to the problem at hand – it looks as though NP complete problems are not all P.

That is, there are some problems that we can show that the proof is correct if we get given one; but finding this proof is not so easy.

(But there was a recent similar proof that had an error. So we wait for the egg-heads to say yay or nay.)

Leave a Reply

Your email address will not be published. Required fields are marked *