If you solve the P=NP? problem that find that P=NP. Dare you announce it publicly?
Ask HN: If you prove that P=NP, dare you announce it?
1–10 of 20 posts
Re: Ask HN: If you prove that P=NP, dare you announce it?
#2Knuth suspects that P=NP. However, theoretical feasibility doesn't necessarily mean that you'll know how to solve NP problems in P time, he says.
Re: Ask HN: If you prove that P=NP, dare you announce it?
#3Purported proofs of P=NP are published multiple times a year. They just always turn out to have a flaw, just like the P≠NP proofs. http://www.win.tue.nl/~gwoegi/P-versus-NP.htm collects them, though it hasn't been updated since 2 May 2015, probably when the refutation of the most recent purported P=NP proof was added.
Re: Ask HN: If you prove that P=NP, dare you announce it?
#4Yes.
Either you have a solution, and that's a great thing, or you are close to a solution and one will be found more quickly and that too is a great thing, or you don't have a solution. That's not such a great thing, but it's a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie.
This assumes you have done the thought work and want to know. Don't you?
Re: Ask HN: If you prove that P=NP, dare you announce it?
#5Yes. Either you have a solution, and that's a great thing, or you are close to a solution and one will be found more quickly and that too is a great thing, or you don't have a solution. That's not such a great thing, but it's a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie. This assumes you have done the thought work and want to know. Don't you?
It's definitely a huge contribution. But P=NP potentially means that RSA is solvable in Polynomial time. Then countless servers will be attackable. Not sure whether it's good to announce "publicly".
Re: Ask HN: If you prove that P=NP, dare you announce it?
#6Yes. Either you have a solution, and that's a great thing, or you are close to a solution and one will be found more quickly and that too is a great thing, or you don't have a solution. That's not such a great thing, but it's a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie. This assumes you have done the thought work and want to know. Don't you?
It's definitely a huge contribution. But P=NP potentially means that RSA is solvable in Polynomial time. Then countless servers will be attackable. Not sure whether it's good to announce "publicly".
Except that if you could figure it out, others probably will soon too - or already did. If countless servers are attackable, or will be soon, should their operators and users be warned or not?
Re: Ask HN: If you prove that P=NP, dare you announce it?
#7Yes. Either you have a solution, and that's a great thing, or you are close to a solution and one will be found more quickly and that too is a great thing, or you don't have a solution. That's not such a great thing, but it's a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie. This assumes you have done the thought work and want to know. Don't you?
It's definitely a huge contribution. But P=NP potentially means that RSA is solvable in Polynomial time. Then countless servers will be attackable. Not sure whether it's good to announce "publicly".
Polynomial time does not necessarily make it easy, the degree of the polynomial could be plenty high making large problems still sufficiently expensive.
Re: Ask HN: If you prove that P=NP, dare you announce it?
#8Earlier quoted context omitted.
It's definitely a huge contribution. But P=NP potentially means that RSA is solvable in Polynomial time. Then countless servers will be attackable. Not sure whether it's good to announce "publicly".
Polynomial time does not necessarily make it easy, the degree of the polynomial could be plenty high making large problems still sufficiently expensive.
It need not even be of high degree. With a large enough constant, even a constant-time algorithm could be way out of reach.
Suppose that somebody shows that, once you are past a googol^googol (not a big number, as numbers in mathematics go), factoring doesn't get harder at all, that would be merely a curiosity in practice (It also would be a hugely surprising result that would inspire mathematicians to start looking for ways to bring that limit down)
Re: Ask HN: If you prove that P=NP, dare you announce it?
#9Yes. Either you have a solution, and that's a great thing, or you are close to a solution and one will be found more quickly and that too is a great thing, or you don't have a solution. That's not such a great thing, but it's a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie. This assumes you have done the thought work and want to know. Don't you?
It's definitely a huge contribution. But P=NP potentially means that RSA is solvable in Polynomial time. Then countless servers will be attackable. Not sure whether it's good to announce "publicly".
No, it's good. There will be latency between the proof and specific attack solutions.
We are better for the warning.
What if someone doesn't announce and has nefarious intent?