【答案】应助回帖

» 猜你喜欢

氨基封端PDMS和HDI反应快速固化已经有11人回复
博士申请都是内定的吗？已经有11人回复
博士读完未来一定会好吗已经有38人回复
谈谈两天一夜的“延安行” 已经有3人回复
之前让一硕士生水了7个发明专利，现在这7个获批发明专利的维护费可从哪儿支出哈？已经有11人回复
论文投稿求助已经有4人回复
Applied Surface Science 这个期刊。有哪位虫友投过的能把word模板发给我参考一下嘛已经有3人回复
投稿精细化工已经有6人回复

» 本主题相关价值贴推荐，对您同样有帮助:

数学史上最富传奇色彩的未解猜想——ABC猜想，来自日本京都大学教授望月新一的证明已经有15人回复
AIM键临界点处电子密度拉普拉斯值符号判断相互作用类型失败原因的图形分析已经有24人回复
【美国派四部曲】 [未分级版].1-4.1999-2012.BluRay.720p/1080p 已经有503人回复
从He2等的量子化学图形解读范德华作用(续三）已经有22人回复
【sobereva个人文集】制作动画分析电子结构特征已经有29人回复

1楼2016-08-24 21:44:38

zzuzrx

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 95
帖子: 32
在线: 38小时
虫号: 2083166
注册: 2012-10-24
专业: 计算机科学

引用回帖:

2楼: Originally posted by congyiyang at 2016-08-24 21:58:27
已经证明 nphard了你是要说别人证的不对？

说错，刚才最后一句是想说，如果证明为NP-C了是不是就可以说，我可以找到多项式时间的算法来验证这个问题了。

4楼2016-08-25 10:59:30

查看全部 9 个回答

congyiyang

银虫 (文坛精英)

应助: 36 (小学生)
金币: 141.4
散金: 4284
红花: 125
沙发: 236
帖子: 11205
在线: 3710.2小时
虫号: 4008472
注册: 2015-08-06
专业: 信号理论与信号处理

已经证明 nphard了你是要说别人证的不对？

发自小木虫IOS客户端

2楼2016-08-24 21:58:27

zzuzrx

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 95
帖子: 32
在线: 38小时
虫号: 2083166
注册: 2012-10-24
专业: 计算机科学

引用回帖:

2楼: Originally posted by congyiyang at 2016-08-24 21:58:27
已经证明 nphard了你是要说别人证的不对？

额，我是刚接触NP这一方面，我看NP-C是要满足两个条件：（1）该问题是个NP问题；（2）其他的NP问题都可以归约到该问题。而NP-hard问题则只需要满足第二条。
我就在想，那对于已经证明为NP-hard问题的，是不是可以通过证明该问题为NP问题，来进一步把它证明为NP-C问题。

因为目前想对一个已经被证明为NP-hard的问题找他的多项式时间近似算法。如果证明为NP-C了是不是就可以说，我找不到多项式时间的算法来验证这个问题了。

3楼2016-08-25 10:22:33

https://upload.wikimedia.org/wik ... omplete_np-hard.svg

FMStation

至尊木虫 (知名作家)

信息EPI: 1
应助: 591 (博士)
贵宾: 0.03
金币: 18097.2
红花: 97
帖子: 8891
在线: 1485.3小时
虫号: 2400059
注册: 2013-04-04
专业: 计算机应用技术

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与，应助指数 +1
zzuzrx(conanwj代发): 金币+10, 感谢应助 2016-09-30 23:15:19

5楼2016-08-25 11:54:13