TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Ask HN: If you prove that P=NP, dare you announce it?

10 点作者 waitingkuo超过 9 年前
If you solve the P=NP? problem that find that P=NP. Dare you announce it publicly?

9 条评论

jepler超过 9 年前
Purported 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. <a href="http:&#x2F;&#x2F;www.win.tue.nl&#x2F;~gwoegi&#x2F;P-versus-NP.htm" rel="nofollow">http:&#x2F;&#x2F;www.win.tue.nl&#x2F;~gwoegi&#x2F;P-versus-NP.htm</a> collects them, though it hasn&#x27;t been updated since 2 May 2015, probably when the refutation of the most recent purported P=NP proof was added.
33a超过 9 年前
Not unless you were very certainly sure it was true. The probability that you got it right and didn&#x27;t mess up some detail is so vanishingly small that it might as well be 0.<p>If you go around shouting about yet another half-baked &quot;solution&quot;, people will think you&#x27;re a crank (and they might even be right). Exercise some restraint, check it and wait.<p>One thing about a positive P=NP proof is that it would necessarily be constructive, so you could try to actually implement it and maybe do some SAT solving competition. If you start stomping the competition, you would get noticed and be in a much stronger position to announce something like this.
评论 #10335083 未加载
balazsdavid987超过 9 年前
A proof that P=NP would go against our everyday experience and it seems so unlikely that it would take you to the Gödelian level of fame and prestige. Would guys in black suits trying to kill you? No. Would you get 100s of job offers? Yes. Go for it, it would be a huge advancement for humanity.<p>Personally, I have a strong feeling that no one will ever prove that P=NP. There&#x27;s that story that out of 100 math professors 10 or so say that P equals NP, but many of them admitted that they just wanted to be controversial. My suspicion is that the existence of P and NP as different complexity groups is a direct consequence of the way Boolean algebra is built up and the way operations are defined, but I far from being an expert on this.
PeterWhittaker超过 9 年前
If I thought I had such a proof (and I expect the proof would be complex, relying on many leading-edge pieces of wildly different branches of mathematics, and therefore comprehensible in the short to medium term to but a few), I would first see if I could develop a practical implementation of the proof for a well-known NP problem, test that out, and see if it worked.<p>If so, I would have that reviewed by trusted colleagues. (&quot;Hey, buddy, I have a P space solution to travelling salesman!&quot; &quot;Get outta town!&quot;, &quot;No seriously...&quot;). That would at least demonstrate that the proof works.<p>Next step? Well, there&#x27;s a bit of the responsible disclosure argument at play: If P=NP and you have a practical implementation of a P-time algorithm for an NP-complete problem, translating that to another will be less work, I should think, than the original proof or the original implementation...<p>...meaning much crypto would break soon after publication. Give the proof and the implementation to 100 well-known and trustworthy mathematicians from around the world, have them agree to your disclosure strategy, then announce what you&#x27;ve got, with their backing, and tell the world that you won&#x27;t publish for 6 months. Or 12. Whatever.<p>The Fields Medal will wait.<p>That will give the world time to adjust to its new reality.
rumcajz超过 9 年前
Knuth suspects that P=NP. However, theoretical feasibility doesn&#x27;t necessarily mean that you&#x27;ll know how to solve NP problems in P time, he says.
评论 #10329534 未加载
评论 #10335407 未加载
ddingus超过 9 年前
Yes.<p>Either you have a solution, and that&#x27;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&#x27;t have a solution. That&#x27;s not such a great thing, but it&#x27;s a contribution to the set of cases not known to be solutions, potentially hinting at where the solution may lie.<p>This assumes you have done the thought work and want to know. Don&#x27;t you?
评论 #10327856 未加载
mcnamaratw超过 9 年前
If just knowing P=NP were enough, for applications people could go ahead and just make the assumption now. The problem is finding an algorithm.
seiji超过 9 年前
No. <a href="http:&#x2F;&#x2F;www.antipope.org&#x2F;charlie&#x2F;blog-static&#x2F;fiction&#x2F;toast&#x2F;toast.html#antibodies" rel="nofollow">http:&#x2F;&#x2F;www.antipope.org&#x2F;charlie&#x2F;blog-static&#x2F;fiction&#x2F;toast&#x2F;to...</a>
pvaldes超过 9 年前
if N=1, yes<p>Can someone explain better the problem for people like me? What is P and what is N here?
评论 #10331611 未加载