4 ms·
It is addressed in the article. The idea is that it is not a good proof. Solving a hard problem with code doesn't mean that you solved the general case. For ex
by GuB-42 8y ago
It is addressed in the article. The idea is that it is not a good proof.
Solving a hard problem with code doesn't mean that you solved the general case. For example your algorithm may work in polynomial time for some specific 3-SAT problems or hashes up to a certain length. It may be huge but it doesn't mean you proved P=NP.
Furthermore, P=NP doesn't mean you can easily solve NP-Complete problems. What if N^100 is the best you can do? It may be polynomial but it is useless. In fact, small steps are expected. And going straight to a workable algorithm is suspicious.
- 12298765 8y agoSure, it doesn't prove that you've solved P=NP, but if you can do that (especially for multiple known hard problems), it seems pretty likely that your suggested solution would be heavily evaluated. I don't think anyone suggested that breaking a single problem proves P=NP, they were just addressing the article, and suggesting a way to convince someone to evaluate your proof..
- erichocean 8y ago> Solving a hard problem with code doesn't mean that you solved the general case. If we're talking about P=NP, 3-SAT is the "general case". That's why I picked it, since all NP problems are reducible to 3-SAT in polynomial time and space.
- jcranmer 8y agoSaying that you solve a specific case of satisfiability problems (e.g., siphash) is not proof that you can solve any 3-SAT problem. Graph coloring is a great example of this phenomenon--graph coloring is NP-hard, but most graphs can be colored very efficiently in polynomial time.