24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 1794  |  回复: 8
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

zzuzrx

新虫 (初入文坛)

[求助] 如果一个已被证明为NP-hard的问题,我再证明其为NP问题,是否能证明其也为NPC问题呢? 已有2人参与

如题,求解!谢谢!
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zzuzrx

新虫 (初入文坛)

引用回帖:
6楼: Originally posted by gen007gen at 2016-08-27 13:38:28
完全正确,如果证明一个NP-hard问题属于NP就证明了这个问题是NP-complete.

谢谢您了!自己“扑通扑通”了将近一年,回过头看自己去年问的问题,感觉好傻,哈哈~现在都搞清楚了,但又出现了很多新的问题,还在NP的坑里挣扎呢
7楼2017-09-04 16:44:29
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 9 个回答

congyiyang

银虫 (文坛精英)

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

发自小木虫IOS客户端
2楼2016-08-24 21:58:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zzuzrx

新虫 (初入文坛)

引用回帖:
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
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zzuzrx

新虫 (初入文坛)

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

说错,刚才最后一句是想说,如果证明为NP-C了是不是就可以说,我可以找到多项式时间的算法来验证这个问题了。
4楼2016-08-25 10:59:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 286求调剂 +3 丢掉懒惰 2026-03-27 6/300 2026-03-27 23:46 by barnett0632
[考研] 275求调剂 +10 Micky11223 2026-03-25 13/650 2026-03-27 22:42 by Micky11223
[考研] 265求调剂11408 +3 刘小鹿lu 2026-03-27 3/150 2026-03-27 20:53 by nihaoar
[考研] 277跪求调剂 +5 1915668 2026-03-27 8/400 2026-03-27 19:53 by WYUMater
[考研] 一志愿南师大0703化学 275求调剂 +4 Ripcord上岸 2026-03-27 4/200 2026-03-27 17:00 by zhyzzh
[考研] 274求调剂 +17 顾九笙要谦虚 2026-03-24 23/1150 2026-03-27 15:16 by caszguilin
[考研] 一志愿郑大085600,310分求调剂 +5 李潇可 2026-03-26 5/250 2026-03-27 11:14 by 不吃魚的貓
[考研] 材料调剂 +8 匹克i 2026-03-23 8/400 2026-03-27 08:11 by hypershenger
[考研] 081200-11408-276学硕求调剂 +4 崔wj 2026-03-26 4/200 2026-03-27 08:04 by chemisry
[考研] 333求调剂 +7 87639 2026-03-21 12/600 2026-03-26 22:08 by 不吃魚的貓
[考研] 321求调剂 +5 材料cailiao 2026-03-21 5/250 2026-03-26 20:41 by fmesaito
[考研] 303求调剂 +6 蓝山月 2026-03-25 6/300 2026-03-25 22:47 by 418490947
[考研] 0854电子信息求调剂 +7 α____ 2026-03-22 9/450 2026-03-25 13:37 by α____
[考研] 300求调剂,材料科学英一数二 +5 leaflight 2026-03-24 5/250 2026-03-24 16:25 by laoshidan
[考研] 一志愿河北工业大学0817化工278分求调剂 +7 jhybd 2026-03-23 12/600 2026-03-24 09:03 by jhybd
[考研] 384求调剂 +3 子系博 2026-03-22 6/300 2026-03-23 21:45 by 子系博
[考研] 328求调剂 +4 LHHL66 2026-03-23 4/200 2026-03-23 14:55 by lbsjt
[考研] 求调剂一志愿海大,0703化学学硕304分,有大创项目,四级已过 +6 幸运哩哩 2026-03-22 10/500 2026-03-22 20:10 by edmund7
[考研] 一志愿北京化工大学070300 学硕336求调剂 +5 vv迷 2026-03-21 8/400 2026-03-22 14:20 by ColorlessPI
[考研] 0703化学调剂 +4 妮妮ninicgb 2026-03-21 4/200 2026-03-21 18:39 by 学员8dgXkO
信息提示
请填处理意见