24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 1800  |  回复: 8

zzuzrx

新虫 (初入文坛)

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

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

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的回帖

FMStation

至尊木虫 (知名作家)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与,应助指数 +1
zzuzrx(conanwj代发): 金币+10, 感谢应助 2016-09-30 23:15:19
5楼2016-08-25 11:54:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

gen007gen

木虫 (正式写手)

【答案】应助回帖

感谢参与,应助指数 +1
完全正确,如果证明一个NP-hard问题属于NP就证明了这个问题是NP-complete.
虫木小
6楼2016-08-27 13:38:28
已阅   回复此楼   关注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的回帖

zzuzrx

新虫 (初入文坛)

引用回帖:
5楼: Originally posted by FMStation at 2016-08-25 11:54:13
https://upload.wikimedia.org/wikipedia/commons/a/a0/P_np_np-complete_np-hard.svg

非常经典的图!!!!谢谢您的回答!
8楼2017-09-04 16:45:00
已阅   回复此楼   关注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的回帖
相关版块跳转 我要订阅楼主 zzuzrx 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 求调剂 +4 研s. 2026-03-25 4/200 2026-03-31 10:05 by fmesaito
[考研] 求调剂,一志愿 南京航空航天大学 ,080500材料科学与工程学硕,总分289分 +9 @taotao 2026-03-29 9/450 2026-03-30 22:29 by 我是小康
[考研] 合肥区域性重点一本招收调剂 +4 6266jl 2026-03-30 4/200 2026-03-30 21:48 by zhuangyan123
[考研] 一志愿郑州大学,080500学硕,总分317分求调剂 +10 举个栗子oi 2026-03-24 11/550 2026-03-30 19:31 by michael2011
[考研] 295材料工程专硕求调剂 +10 1428151015 2026-03-27 10/500 2026-03-30 19:00 by 源_2020
[考研] 化学308分调剂 +7 你好明天你好 2026-03-30 8/400 2026-03-30 13:02 by 你好明天你好
[硕博家园] 求调剂 有机化学考研356分 +10 Nadiums 2026-03-25 11/550 2026-03-30 11:56 by yjolah
[考研] 环境科学与工程334分求调剂 +6 王一一依依 2026-03-30 8/400 2026-03-30 11:52 by yjolah
[考研] 275求调剂 +15 Micky11223 2026-03-25 20/1000 2026-03-29 20:44 by 唐沐儿
[考研] 调剂310 +12 温柔的晚安 2026-03-25 13/650 2026-03-29 20:01 by 无际的草原
[考研] 085600,专业课化工原理,321分求调剂 +5 大馋小子 2026-03-28 5/250 2026-03-29 08:56 by qingfeng258
[考研] 材料277求调剂 +7 min3 2026-03-24 7/350 2026-03-28 11:39 by xuxiang
[考研] 279 分 求调剂 +4 睡个好觉_16 2026-03-24 4/200 2026-03-27 15:05 by 醉在风里
[考研] 复试调剂,一志愿南农083200食品科学与工程 +5 XQTJZ 2026-03-26 5/250 2026-03-27 14:49 by 狂炫麦当当
[考研] 考研调剂 +10 呼呼?~+123456 2026-03-24 10/500 2026-03-27 11:46 by wangjy2002
[考研] 081200-11408-276学硕求调剂 +4 崔wj 2026-03-26 4/200 2026-03-27 08:04 by chemisry
[考研] 调剂 +4 柚柚yoyo 2026-03-26 4/200 2026-03-26 20:43 by fmesaito
[考研] 打过很多竞赛,085406控制工程300分,求调剂 +3 askeladz 2026-03-26 3/150 2026-03-26 09:08 by 给你你注意休息
[考研] 求调剂 +3 李李不服输 2026-03-25 3/150 2026-03-25 13:03 by cmz0325
[考研] 340求调剂 +5 话梅糖111 2026-03-24 5/250 2026-03-25 06:53 by ilovexiaobin
信息提示
请填处理意见