24小时热门版块排行榜

>论坛更新日志 (3590)
>虫友互识 (266)
>基金申请 (113)
>导师招生 (111)
>文献求助 (88)
>博后之家 (76)
>考博 (70)
>找工作 (69)
>休闲灌水 (53)
>论文道贺祈福 (52)
>论文投稿 (52)
>硕博家园 (48)
>公派出国 (45)
>考研 (32)
>教师之家 (30)
>外文书籍求助 (13)

返回列表

zzuzrx

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 95
帖子: 32
在线: 38小时
虫号: 2083166
注册: 2012-10-24
专业: 计算机科学

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

如题，求解！谢谢！

回复此楼

» 猜你喜欢

面上提前没消息，有中的吗已经有9人回复
售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急已经有12人回复
面上再次挂了，太难了，躺也躺不了，倦也卷不过，小学校之殇！已经有23人回复
售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急已经有13人回复
售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急已经有16人回复
售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急已经有14人回复
售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急已经有17人回复
2026年国自然面上资助率已经有21人回复
基础研究怎么拉横向，学校到款任务越来越多，难以完成拉横向，都有哪些途径啊已经有10人回复
2027年申博已经有3人回复

» 本主题相关价值贴推荐，对您同样有帮助:

数学史上最富传奇色彩的未解猜想——ABC猜想，来自日本京都大学教授望月新一的证明已经有15人回复
AIM键临界点处电子密度拉普拉斯值符号判断相互作用类型失败原因的图形分析已经有24人回复
【美国派四部曲】 [未分级版].1-4.1999-2012.BluRay.720p/1080p 已经有503人回复
从He2等的量子化学图形解读范德华作用(续三）已经有22人回复
【sobereva个人文集】制作动画分析电子结构特征已经有29人回复

1楼 2016-08-24 21:44:38

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

congyiyang

银虫 (文坛精英)

应助: 36 (小学生)
金币: 142.4
散金: 4284
红花: 125
沙发: 236
帖子: 11205
在线: 3710.2小时
虫号: 4008472
注册: 2015-08-06
专业: 信号理论与信号处理

已经证明 nphard了你是要说别人证的不对？

发自小木虫IOS客户端

赞一下

回复此楼

2楼2016-08-24 21:58:27

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

zzuzrx

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 95
帖子: 32
在线: 38小时
虫号: 2083166
注册: 2012-10-24
专业: 计算机科学

引用回帖:

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