-
P != np
Vinay Dolalikar claims to have proven that P!=NP. So he get's a million dollars if the proof holds up for two years.
This is pretty phenomenal if it's true.
What I'm most impressed by is that in his description of it on his website, he didn't include the text "TOP THIS BEOTCHES"
-
For those of us who don't know, what do P and np stand for? P usually denotes momentum.
-
I actually proved this with MATLAB ages ago;
I hope he's right, it's awesome to see these fundamental developments. Hopefully he actually claims the prize this time.
It's funny though, pretty much everybody knew it couldn't be true.
Also funny is how this proof would be a good example that P != NP.
-
@Ninja,
P is the set of problems for which there exist an algorithm for its solution that runs in polynomial time. The polynomial is taken to be in the amount of input elements of the algorithm
NP is the set of problems for which, given an alleged solution, there exists an algorithm to verity it's correctness in polynomial time.
So what da kine did is show that there exists a (large) class of problems for which it is cheap and easy to check solutions but for which it is impossible to find some k, however large, such that there exists an algorithm that computes the solution from scratch in O(nk). O(f(n)) means that the running time of the algorithm is bounded by f(n) as n approaches infinity.
-
-
That would be utterly phenomenal.
Where exactly is the proof or anything about the proof? I checked the site you linked to but I can't seem to find anything related to it.
EDIT: Never mind, I found it.
For anyone else who is interested, here's the proof (PDF):
http://www.win.tue.nl/~gwoegi/P-vers...Deolalikar.pdf
-
The guy took it off. Might not be a good sign. A few people claim to have found flaws, but it remains to be seen if they are genuine, or if they are fixable.
-
FWIW, the paper is back up so I guess he fixed it. Have a PDF
-
I grow more and more sceptical of the proof. A lot of people have pointed out flaws and now even Immerman says that he has found a serious hole. The P=NP?-problem may not be solved yet after all.