首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >假设一个P=NP证明是什么样子的?

假设一个P=NP证明是什么样子的?
EN

Stack Overflow用户
提问于 2009-05-22 22:31:58
回答 11查看 5.6K关注 0票数 17

对于特定的NP-完全问题,它将是一个多项式时间算法,还是仅仅是证明存在NP-完全问题的解决方案的抽象推理?

看起来,特定的算法更有帮助。有了它,我们要做的就是将一个NP问题转化为证明有解的特定NP-完全问题,然后我们就完成了。

EN

回答 11

Stack Overflow用户

发布于 2009-05-22 22:49:22

你可以说我悲观,但事情会是这样的:

..。

∴,P≠NP

QED

票数 17
EN

Stack Overflow用户

发布于 2009-05-22 23:00:22

它可以采取证明假设P≠NP导致矛盾的形式。

票数 5
EN

Stack Overflow用户

发布于 2009-05-22 23:03:24

它可能不会以一种直接的方式连接到P和NP ...现在许多定理都是基于P!=NP的,所以证明一个假设的事实是不正确的将会有很大的不同。即使证明了TS的常数比率近似,也应该足够IIRC。我认为,NPI (GI)和其他集合的存在也是基于P!=NP的,所以使它们中的任何一个等于P或NP都可能完全改变这种情况。

现在一切都发生在一个非常抽象的层次上。如果有人证明了关于P=/!=NP的任何东西,它就不需要提到这些集合中的任何一个,甚至不需要提到特定的问题。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/900273

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档