Hacker News Reader

Comment by erichocean | Hacker News Reader

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…

View on HN

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.

Sure, 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..

> 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.

Saying 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.

That's a good idea, but it won't work for a non-constructive proof.

Nor 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”.

I 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).

An 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_... had first a bad polynomial complexity and was later improved in other papers.

Does having a proof of P=NP necessarily mean that you can write the code to solve NP problems though?

Not necessarily, but it's hard for me to imagine what a non-constructive proof of P=NP would look like.

> 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%9...

Interesting. Thanks!

What do you image a constructive proof looking like?

It would look like an algorithm that solves an NP-complete problem in polynomial time. (Isn't that obvious?)

Sure. And why does that seem any more feasible than a non-constructive proof?

I don't know. Why is the moon plaid?

Reply on news.ycombinator.com