24小时热门版块排行榜    

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

zzuzrx

新虫 (初入文坛)

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

如题,求解!谢谢!
回复此楼
已阅   回复此楼   关注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的回帖
查看全部 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的回帖

FMStation

至尊木虫 (知名作家)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感谢参与,应助指数 +1
zzuzrx(conanwj代发): 金币+10, 感谢应助 2016-09-30 23:15:19
5楼2016-08-25 11:54:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 材料调剂 +8 匹克i 2026-03-23 8/400 2026-03-27 08:11 by hypershenger
[考研] 考研调剂 +9 呼呼?~+123456 2026-03-24 9/450 2026-03-27 03:47 by wxiongid
[考研] 349求调剂 +5 杰斯塔里斯 2026-03-21 5/250 2026-03-27 00:31 by wxiongid
[考研] 一志愿郑州大学,080500学硕,总分317分求调剂 +4 举个栗子oi 2026-03-24 5/250 2026-03-26 23:15 by 不吃魚的貓
[考研] 333求调剂 +6 wfh030413@ 2026-03-23 6/300 2026-03-26 22:45 by 学员8dgXkO
[考研] 311求调剂 +5 lin0039 2026-03-26 5/250 2026-03-26 22:43 by 学员8dgXkO
[考研] 求调剂 +6 白QF 2026-03-21 6/300 2026-03-26 20:37 by fmesaito
[考研] 一志愿厦门大学化学学硕307求调剂 +8 y7czhao 2026-03-26 8/400 2026-03-26 19:51 by 不吃魚的貓
[考研] 0703化学/290求调剂/本科经历丰富/工科也可 +7 丹青奶盖 2026-03-26 7/350 2026-03-26 19:18 by macy2011
[考研] 总分293求调剂 +6 加一一九 2026-03-25 8/400 2026-03-26 13:30 by yujianx
[考研] 求调剂一志愿武汉理工大学材料工程(085601) +5 WW.' 2026-03-23 7/350 2026-03-24 14:50 by sprinining
[考研] 305分求调剂(食品工程) +5 Sxy112 2026-03-21 7/350 2026-03-24 12:27 by 544594351
[考研] 一志愿吉大化学322求调剂 +4 17501029541 2026-03-23 6/300 2026-03-24 10:21 by 戴围脖的小蚊子
[考研] 276求调剂。有半年电池和半年高分子实习经历 +9 材料学257求调剂 2026-03-23 10/500 2026-03-24 07:36 by wangy0907
[考研] 环境学硕288求调剂 +8 皮皮皮123456 2026-03-22 8/400 2026-03-23 23:47 by 热情沙漠
[考研] 361求调剂 +3 Glack 2026-03-22 3/150 2026-03-23 22:03 by fuyu_
[考研] 276求调剂 +3 YNRYG 2026-03-21 4/200 2026-03-23 08:31 by 醉在风里
[考研] 315分,诚求调剂,材料与化工085600 +3 13756423260 2026-03-22 3/150 2026-03-22 20:11 by edmund7
[考研] 一志愿华中农业071010,总分320求调剂 +5 困困困困坤坤 2026-03-20 6/300 2026-03-22 17:41 by hxsm
[考研] 353求调剂 +3 拉钩不许变 2026-03-20 3/150 2026-03-20 19:56 by JourneyLucky
信息提示
请填处理意见