24小时热门版块排行榜    

查看: 1667  |  回复: 7
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

chentianyu1

木虫 (小有名气)

[求助] 关于图论问题的NP完备性证明

现在要证明一个图论问题是NP-Complete,是否只需证明它对于某些特殊拓扑的图(比如弦图、二部图)是NP-Complete的?如果答案是肯定的,请给出一个此类证明的例子。
个人感觉特殊拓扑的图是NP-Complete不能说明这个问题就是NP-Complete,否则我们平时用NP-Complete来判别问题的复杂程度就没意义了。
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ftai

金虫 (著名写手)

  从密码学的角度来看,NP+组合图论+密码算法,很值得研究。这是个应会出创新而有价值成果的方向。
4楼2012-11-11 18:50:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 8 个回答

ftai

金虫 (著名写手)

  《图论》和《组合(数学)图论》中的NP难题似乎比较多。
  正在分析中:也许可以使用其中的一些NP难题用于设计非对称加密解密算法。类似于RSA等,非对称加密解密算法主要是基于如:大数分解,离散对数,背包问题,以及椭圆曲线难题的。

  一般有两种办法来证明某个问题是NP难的:
1、非确定性图灵机可验证的。
2、可映射归约到另一个NP难题。

例如,采用方法1来证明第一个被发现的NP难题:3-SAT问题。它描述了:由多个三析取范式取合取,
例如:(P1或P2或P3)与(P2或P3或P5)……(p1 | p2 | p3) ^ (p2 | p3 |p5)……,看结果值是否为真值。
如果输入P有20个引脚,就有2^20种可能,必须一个一个布尔函数去试;
如果输入P有30个引脚,就必须遍历2^30次来计算多个三析取范式是否的结果值是否为真值,同样必须一个一个布尔函数去试。
它显然是组合爆炸的。
在实际的布尔逻辑与安全的研究中,还明确了排列数N!甚至比指数2^N的计算量更大。
证明它是NP难题很简单:给定一个例子,它是非确定性图灵机可验证的。
2楼2012-11-11 18:01:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chentianyu1

木虫 (小有名气)

引用回帖:
2楼: Originally posted by ftai at 2012-11-11 18:01:33
  《图论》和《组合(数学)图论》中的NP难题似乎比较多。
  正在分析中:也许可以使用其中的一些NP难题用于设计非对称加密解密算法。类似于RSA等,非对称加密解密算法主要是基于如:大数分解,离散对数 ...

抱歉,没能理解您的回复与我提出的问题之间的关系。
3楼2012-11-11 18:34:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chentianyu1

木虫 (小有名气)

引用回帖:
4楼: Originally posted by ftai at 2012-11-11 18:50:02
  从密码学的角度来看,NP+组合图论+密码算法,很值得研究。这是个应会出创新而有价值成果的方向。

好吧,不过这还是没有回答我的问题。
5楼2012-11-11 19:56:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[论文投稿] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-19 00:17 by Equinoxhua
[教师之家] 征友后感触 +5 重新启 2026-11-17 6/300 2026-11-18 21:22 by tjutjulee
[教师之家] 为了不被淘汰,必须要开始第三次奋斗了 +4 lice_1987 2026-11-15 6/300 2026-11-18 21:19 by tjutjulee
[考博] 27博士申请(市政/环境) +4 ladf 2026-11-12 4/200 2026-11-18 20:18 by junqiang
[找工作] 售SCI一区T0P文章,我:8.O.55.1.O54,科目全,可伽急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-18 14:51 by UPDUsNlULsJZ
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 SX5mJmPWDfOO 2026-11-13 4/200 2026-11-18 13:55 by UPDUsNlULsJZ
[硕博家园] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +5 SX5mJmPWDfOO 2026-11-13 6/300 2026-11-18 13:33 by UPDUsNlULsJZ
[考博] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-18 13:22 by UPDUsNlULsJZ
[硕博家园] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-18 11:32 by Z1pODz48hoDV
[考博] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 10:37 by Z1pODz48hoDV
[公派出国] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +4 uKOSCocCb6Fm 2026-11-12 8/400 2026-11-18 09:53 by Z1pODz48hoDV
[考研] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +4 uKOSCocCb6Fm 2026-11-12 6/300 2026-11-18 09:31 by Z1pODz48hoDV
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 7/350 2026-11-18 09:09 by Z1pODz48hoDV
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 uKOSCocCb6Fm 2026-11-12 9/450 2026-11-18 09:06 by Equinoxhua
[硕博家园] 售SCI文章,我:8O.5.5.1O.54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 10/500 2026-11-16 22:49 by Equinoxhua
[考博] 27年药学 考博申请 +4 。12345 2026-11-14 5/250 2026-11-16 19:52 by 0611517sll
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-16 11:06 by K7HMGGdOpylw
[公派出国] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-15 08:29 by xSrQNSSjcgoX
[硕博家园] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +4 XJXMuRjD7cK7 2026-11-13 4/200 2026-11-15 06:50 by xSrQNSSjcgoX
[考博] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +3 uKOSCocCb6Fm 2026-11-12 7/350 2026-11-15 03:32 by xSrQNSSjcgoX
信息提示
请填处理意见