11–20 of 156 posts
Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
It's on the arXive, so you know it's legit.
I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"
You're wrong. 3-SAT is NP-complete.
Quoting Wikipedia:
"But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general."
OK, I just upvoted purely for the reason of keeping it on the front page a little longer so someone more qualified has a chance to glance at this. Without any evidence and no qualification to judge myself, it seems highly unlikely.
If I write a paper formatted in LaTeX saying that I cloned a T-Rex in my backyard, should it be upvoted so that an expert in cloning can take a look at it?
I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"
Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
This particular attempt involves someone claiming P=NP, and they have code. Even people who aren't complexity theorists can jump in on this one, by analyzing the code to verify it really is in P, and by trying to find problem instances it fails on.
I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"
http://en.wikipedia.org/wiki/3SAT#3-satisfiability http://en.wikipedia.org/wiki/NP-complete
Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
However, this guy seems very cool - he is humble about his work, appears very serious, and even puts his code on github. And even if wrong, his approach might be interesting.
Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon.
1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them.
2. Most 3SAT problems are "easy". Being able to solve a particular problem doesn't mean that the algorithm works in general. He would have done better to demonstrate his algorithm on "known hard" problems.
3. He states a running time of O(n^4 m), but his experimental results don't scale quite like this; perhaps his analysis is wrong, or perhaps there's just a monster hiding behind the big-O.
4. If he is correct, and his algorithm is optimal, we probably don't need to worry very much about cryptography yet: It looks like this algorithm is far too slow to be a practical attack on existing cryptosystems.
(EDIT: Oops, in the time it took me to write that, 18 other people posted comments. Well, so much for getting the discussion started...)