24小时热门版块排行榜    

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

zzuzrx

新虫 (初入文坛)

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

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

gen007gen

木虫 (正式写手)

引用回帖:
7楼: Originally posted by zzuzrx at 2017-09-04 16:44:29
谢谢您了!自己“扑通扑通”了将近一年,回过头看自己去年问的问题,感觉好傻,哈哈~现在都搞清楚了,但又出现了很多新的问题,还在NP的坑里挣扎呢...

不客气,希望我的回答对你有帮助,也祝你顺利解决新的问题。
虫木小
9楼2017-09-05 15:17:04
已阅   回复此楼   关注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的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 284求调剂 +10 junqihahaha 2026-03-26 11/550 2026-03-27 01:15 by yhmsz
[考研] 349求调剂 +5 杰斯塔里斯 2026-03-21 5/250 2026-03-27 00:31 by wxiongid
[考研] 0703化学338求调剂! +5 Zuhui0306 2026-03-26 6/300 2026-03-26 23:42 by 381988266
[考研] 305求调剂 +4 哇卢卡库 2026-03-26 4/200 2026-03-26 20:58 by sanrepian
[考研] 调剂 +4 柚柚yoyo 2026-03-26 4/200 2026-03-26 20:43 by fmesaito
[考研] 329求调剂 +5 1() 2026-03-22 5/250 2026-03-26 20:40 by fmesaito
[考研] 0703化学/290求调剂/本科经历丰富/工科也可 +7 丹青奶盖 2026-03-26 7/350 2026-03-26 19:18 by macy2011
[考研] 一志愿211 初试270分 求调剂 +6 谷雨上岸 2026-03-23 7/350 2026-03-26 18:55 by 不吃魚的貓
[考研] 303求调剂 +6 蓝山月 2026-03-25 6/300 2026-03-25 22:47 by 418490947
[考研] 求调剂 +3 QiMing7 2026-03-25 3/150 2026-03-25 21:13 by 给你你注意休息
[考研] 26考研-291分-厦门大学(085601)-柔性电子学院材料工程专业求调剂 +3 min3 2026-03-24 4/200 2026-03-25 18:22 by xcjcqu
[考研] 考研化学308分求调剂 +10 你好明天你好 2026-03-23 11/550 2026-03-25 10:23 by userper
[考研] 318求调剂 +3 plum李子 2026-03-23 3/150 2026-03-25 09:42 by 雾散后相遇lc
[考研] 306求0703调剂一志愿华中师范 +10 纸鱼ly 2026-03-21 11/550 2026-03-24 17:22 by qingfeng258
[考研] 材料/农业专业,07/08开头均可,过线就行 +3 呵唔哦豁 2026-03-23 4/200 2026-03-23 22:30 by 汪!?!
[考研] 求老师收我 +3 zzh16938784 2026-03-23 3/150 2026-03-23 12:56 by ztnimte
[考研] 生物学调剂 +5 Surekei 2026-03-21 5/250 2026-03-22 14:39 by tcx007
[考研] 297求调剂 +3 喜欢还是不甘心 2026-03-20 3/150 2026-03-21 18:33 by 学员8dgXkO
[考研] 0805材料320求调剂 +3 深海物语 2026-03-20 3/150 2026-03-21 15:46 by 无际的草原
[考研] A区线材料学调剂 +5 周周无极 2026-03-20 5/250 2026-03-20 21:33 by laoshidan
信息提示
请填处理意见