24小时热门版块排行榜    

查看: 1996  |  回复: 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 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 为什么资助数各大高校都创新高,自己申请怎么就这么难 +3 Kittylucky 2026-08-27 3/150 2026-08-27 11:12 by marinewhale
[基金申请] 面上合作单位盖章 +3 ssyjh 2026-08-27 3/150 2026-08-27 09:59 by 阿拉贡aragon
[基金申请] 基金不中,共勉 +7 eulota 2026-08-26 7/350 2026-08-27 09:02 by hsding2026
[基金申请] 怎么查啊 +5 huang1991js 2026-08-26 5/250 2026-08-26 16:09 by Equinoxhua
[基金申请] 范进中举一文的中心思想 +9 炎黄贵胄 2026-08-22 10/500 2026-08-26 15:40 by semaglutide
[基金申请] 2026国自然函评费到账 +22 羊腰板 2026-08-21 25/1250 2026-08-26 15:00 by zuocuiping
[基金申请] 2026年8月25日国自然放榜前突然收到列入评审专家邮件,有关系吗? +25 木水思豆 2026-08-25 28/1400 2026-08-26 14:53 by draco1987
[基金申请] 国合里面能看到了 +7 一怀馨秋 2026-08-26 7/350 2026-08-26 11:23 by zhaosm1982
[基金申请] 系统进不去 +4 yanglien 2026-08-26 5/250 2026-08-26 11:10 by wenfengw83
[基金申请] 今天务委会开完了,明天出结果吗 +19 angus9576 2026-08-25 23/1150 2026-08-26 10:03 by zp519
[基金申请] 牛来!米来!面来! +8 beefly 2026-08-26 8/400 2026-08-26 08:37 by xuzhipiao
[基金申请] 明天应该可查了!? +6 chengyan1220 2026-08-23 6/300 2026-08-25 19:45 by zfd97
[基金申请] 如果此刻你正在为国基感到焦虑,不妨来听听这首《基金之外》 +8 scalable 2026-08-24 8/400 2026-08-25 12:52 by jnhyjjm
[基金申请] 人气不行了 +11 fansofjerry 2026-08-21 11/550 2026-08-25 11:04 by 孤独的英雄6
[基金申请] 建议基金发布提前给出明确的时间点 +13 kulium 2026-08-21 16/800 2026-08-24 16:27 by superceng
[教师之家] 跳槽后在研项目怎么办? +5 简单化xn 2026-08-22 10/500 2026-08-23 12:38 by 简单化xn
[基金申请] 时间戳今天,20号变了 +5 archvillain 2026-08-20 5/250 2026-08-22 06:12 by hui_daxiao
[基金申请] 看来今天不会放榜了? +8 chengyan1220 2026-08-21 11/550 2026-08-21 17:52 by dcqxinyang
[基金申请] 时间戳又变了 +13 wuchongjun 2026-08-20 19/950 2026-08-21 17:21 by 紫杉醇
[基金申请] 应该是下周三26日公布了吧? +4 哈哈蛤? 2026-08-21 4/200 2026-08-21 10:58 by Vivilian
信息提示
请填处理意见