'Hardest' maths problem 'solved'

LionelNashe

From a story in today's Indo, that originally came from the Telegraph

Vinay Deolalikar, who works at the research arm of Hewlett-Packard in Palo Alto, California, believes he has solved the riddle of P vs NP in a move that could transform mankind’s use of computers as well as earn him a $1m (£650,000) prize.

"P vs NP"is one of the seven millennium problems set out by the Massachusetts-based Clay Mathematical Institute as being the “most difficult” to solve......


The published paper is here.
I don't understand the paper, or what the implications are, but I will be following the story to see what happens if it holds up. I was wondering what people's opinions are. If Paddy Power were offering bets on the guy's proof being correct, what odds would you look for?

LeixlipRed

It'd change the world simply put.

elementary

It's certainly not correct as it is, according to the experts. There is a chance that the ideas used might lead to a proof.

I don't bet on things if I don't know that the odds are in my favour... and haven't a clue what the odds are here... but my hunch would be that if anything comes of this it'd be to do with the fact that many of the top mathematicians in the world are actively discussing this particular problem at the moment.

Enkidu

He has surprised people more in the method of his attempt than anything else. He had the interesting idea of trying to use techniques from statistical mechanics rather than computational complexity theory and since P = NP is a problem in complexity theory this a rather novel idea. Complexity theorists are saying that even if his proof isn't correct it is still full of innovative thinking.

He is claiming that he has proved P != NP which almost all mathematicians consider more likely than P = NP.

If anybody is wondering, P stand for Polynomial time. It's basically the set of all problems which can be solved quickly. More technically, if n is the size of the input, the time generated to obtain the output is a polynomial (and not something like an exponential) in n.

NP is non-deterministic polynomial time. It is essentially the set of problems where you can check if the the answer is correct quickly.

So:
P is computational problems where you can compute the answer fast.
NP is computational problems where you can check if the answer is right fast.

Now one would imagine that it's much easier to check if an answer is right than to actually compute it. The idea is that there are several problems in computing which aren't in P because their answers are hard to compute, but they are in NP because their answers are easy to check.

The question posed for the problem is asking if P = NP. Which means that any problem for who the answer is easy to check, will ultimately have some easy way of actually working out the answer.

In coding language, if you have some piece of code that works something out, P = NP would mean that if it is easy to check that the answer generated by the code is correct, then there must be a way to rewrite the code to perform the task as fast as you can check the answer.

Most people believe P != NP, which basically means there are some problems for which it is an unavoidable fact that the answer is easier to check than it is to compute.

Enkidu

It would appear that it is most likely that he has not proved that P != NP.
See:
http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/#comment-4885

LionelNashe

Enkidu wrote: »

He is claiming that he has proved P != NP which almost all mathematicians consider more likely than P = NP.

Oh. I missed that even though its the title of his paper. I thought he had proved the opposite.

ray giraffe

LeixlipRed wrote: »

It'd change the world simply put.

According to wikipedia, a proof that P=NP would have major effects, a proof that P≠NP (as is claimed) would not.

A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.

So it would change the world for thousands of complexity theorists, no effect for 99.999% of people.

- It would probably not even affect the vast majority of mathematicians or computer scientists.

RoundTower

even a proof that P=NP might not be all that practically useful, since a solution in polynomial time can still be slow in practice. What if all the interesting problems could be solved in time proportional to the billionth power of x, or more? It might also be an existence proof rather than a construction proof so it wouldn't spit out a polynomial-time algorithm for any NP problem.

Enkidu

RoundTower wrote: »

even a proof that P=NP might not be all that practically useful, since a solution in polynomial time can still be slow in practice. What if all the interesting problems could be solved in time proportional to the billionth power of x, or more? It might also be an existence proof rather than a construction proof so it wouldn't spit out a polynomial-time algorithm for any NP problem.

Personally, I would say it is very likely that it would be a pure existence proof. At least judging by the history of the area.