24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 1798  |  回复: 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的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 274求调剂 +4 xiao爱同学 2026-03-30 4/200 2026-03-31 00:04 by jp9609
[考研] 一志愿中海洋320化学工程与技术学硕求调剂 +3 披星河 2026-03-30 3/150 2026-03-30 23:38 by 果果妈咪
[考研] 调剂 +4 GK72 2026-03-30 4/200 2026-03-30 20:32 by dick_runner
[考研] 322求调剂 +10 宋明欣 2026-03-27 10/500 2026-03-30 18:47 by 544594351
[考研] 297求调剂 +17 田洪有 2026-03-26 18/900 2026-03-30 18:32 by nothing投稿中
[考研] 332求调剂 +6 @MZB382400 2026-03-28 6/300 2026-03-30 16:57 by 无际的草原
[考研] 324求调剂 +9 hanamiko 2026-03-26 11/550 2026-03-30 14:27 by JourneyLucky
[考研] 071010 323 分求调剂 +3 Baekzhy 2026-03-27 3/150 2026-03-30 14:24 by andresqi
[考研] 070300化学354求调剂 +7 101次希望 2026-03-28 7/350 2026-03-30 13:22 by Iveryant
[考研] 296求调剂 +10 彼岸t 2026-03-29 10/500 2026-03-30 10:50 by 探123
[考研] 348求调剂 +6 小懒虫不懒了 2026-03-28 6/300 2026-03-30 10:29 by Evan_Liu
[考研] 290求调剂 +3 dfffsar 2026-03-29 3/150 2026-03-29 22:38 by 毛毛毛阿莫2
[考研] 081200-11408-276学硕求调剂 +6 崔wj 2026-03-26 6/300 2026-03-29 01:11 by hanserlol
[考研] 343求调剂 +5 爱羁绊 2026-03-28 5/250 2026-03-28 20:53 by 唐沐儿
[考研] 347求调剂 +3 山顶见α 2026-03-25 3/150 2026-03-28 14:13 by 唐沐儿
[材料工程] 一志愿C9材料与化工专业总分300求调剂 +8 曼111 2026-03-24 9/450 2026-03-28 07:58 by YYYYX1234
[有机交流] 高温高压反应求助 10+4 chibby 2026-03-25 4/200 2026-03-27 21:08 by BT20230424
[考研] 调剂 +4 柚柚yoyo 2026-03-26 4/200 2026-03-26 20:43 by fmesaito
[考研] 机械学硕总分317求调剂!!!! +4 Acaciad 2026-03-25 4/200 2026-03-25 19:59 by hanserlol
[考研] 一志愿武理085500机械专业总分300求调剂 +3 an10101 2026-03-24 7/350 2026-03-25 00:00 by 山鬼0-
信息提示
请填处理意见