5 ms·
If you have a proof that P=NP, the best way to demonstrate that is to solve a nice, hard 3-SAT problem. Maybe reversing something like siphash, or something sim
by erichocean 8y ago
If you have a proof that P=NP, the best way to demonstrate that is to solve a nice, hard 3-SAT problem. Maybe reversing something like siphash, or something similarly difficult.
Set up a web page where someone can put in their 128-bit SIP hash and their plaintext, and you'll tell them the 64-bit secret used to hash it.
Everyone will believe you.
For extra bonus $$$, there are various large prizes (e.g. $1M USD) you can win if you can "break" various things which are trivially breakable if P=NP. Might as well cash in there, too before they pull the plug on the contest…
- lisper 8y agoThat's a good idea, but it won't work for a non-constructive proof.
- kelnage 8y agoNor would it necessarily work (quickly) if the order of magnitude for any constants were sufficiently large (after all, a runtime of 2 * N and a runtime of (2^512) * N are both O(N)). If I remember correctly, in the semi-regular survey conducted with CS experts about this question, the most likely explanation that accompanied a response saying they believed that it may be the case that P=NP was “...but with very large constants”.
- erichocean 8y agoI personally distrust all non-constructive proofs as a matter of principle, and can't think of a single one I would actually miss in practice, let alone one I find convincing. They all smack of begging the question to me. I especially distrust non-constructive proofs that involve first constructing objects in an impossible manner (like, say, sorting an infinite set of infinitely long bit strings—I'm looking at you, Cantor)—and then (ab-)using the reader's intuition about actual things you can construct to "prove" nonsense about things you clearly can't. Which is a long way of saying that I'll only accept a constructive proof that P != NP (or vice versa).
- deleted 8y ago[deleted]
- vermilingua 8y agoDoes having a proof of P=NP necessarily mean that you can write the code to solve NP problems though?
- lisper 8y agoNot necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like.
- sidusknight 8y agoWhat do you image a constructive proof looking like?
- lisper 8y agoIt would look like an algorithm that solves an NP-complete problem in polynomial time. (Isn't that obvious?)
- sidusknight 8y agoSure. And why does that seem any more feasible than a non-constructive proof?
- lisper 8y agoI don't know. Why is the moon plaid?
- wolfgke 8y ago> Not necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like. Have a look at the proof of the Robertson-Seymour theorem. Here the Wikipedia section about its importance in complexity theory: > https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%93Seymour_theorem&oldid=867644170#Polynomial_time_recognition https://en.wikipedia.org/w/index.php?title=Robertson%E2%80%9...
- jknz 8y agoAn algorithm with complexity O(n^{999}) is polynomial but but not more useful than an exponential algorithm on any practical problem. If an NP solver comes out, it may not practical (at first or for any practical purposes). The polynomial complexity of the "P is in prime" algorithm https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf https://www.cse.iitk.ac.in/users/manindra/algebra/primality_... had first a bad polynomial complexity and was later improved in other papers.
- GuB-42 8y agoIt 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.