| 查看: 1136 | 回复: 7 | |||
chentianyu1木虫 (小有名气)
|
[求助]
关于图论问题的NP完备性证明
|
|
现在要证明一个图论问题是NP-Complete，是否只需证明它对于某些特殊拓扑的图（比如弦图、二部图）是NP-Complete的？如果答案是肯定的，请给出一个此类证明的例子。 个人感觉特殊拓扑的图是NP-Complete不能说明这个问题就是NP-Complete，否则我们平时用NP-Complete来判别问题的复杂程度就没意义了。 |
回复此楼» 猜你喜欢
论文终于录用啦！满足毕业条件了
已经有21人回复
-
不自信的我
已经有5人回复
-
磺酰氟产物，毕不了业了！
已经有4人回复
-
投稿Elsevier的杂志（返修），总是在选择OA和subscription界面被踢皮球
已经有8人回复
ftai
金虫 (著名写手)
- 应助: 19 (小学生)
- 金币: 7740.8
- 散金: 574
- 红花: 7
- 帖子: 1399
- 在线: 355.5小时
- 虫号: 2101685
- 注册: 2012-11-02
- 性别: GG
- 专业: 信息安全
|
《图论》和《组合（数学）图论》中的ＮＰ难题似乎比较多。 正在分析中：也许可以使用其中的一些ＮＰ难题用于设计非对称加密解密算法。类似于ＲＳＡ等，非对称加密解密算法主要是基于如：大数分解，离散对数，背包问题，以及椭圆曲线难题的。 一般有两种办法来证明某个问题是ＮＰ难的： １、非确定性图灵机可验证的。 ２、可映射归约到另一个ＮＰ难题。 例如，采用方法１来证明第一个被发现的ＮＰ难题：３－ＳＡＴ问题。它描述了：由多个三析取范式取合取， 例如：（Ｐ１或Ｐ２或Ｐ３）与（Ｐ２或Ｐ３或Ｐ５）……(p1 | p2 | p3) ^ (p2 | p3 |p5)……，看结果值是否为真值。 如果输入Ｐ有２０个引脚，就有２^２０种可能，必须一个一个布尔函数去试； 如果输入Ｐ有３０个引脚，就必须遍历２^３０次来计算多个三析取范式是否的结果值是否为真值，同样必须一个一个布尔函数去试。 它显然是组合爆炸的。 在实际的布尔逻辑与安全的研究中，还明确了排列数Ｎ！甚至比指数２^Ｎ的计算量更大。 证明它是ＮＰ难题很简单：给定一个例子，它是非确定性图灵机可验证的。 |
2楼2012-11-11 18:01:33
chentianyu1
木虫 (小有名气)
- 应助: 67 (初中生)
- 金币: 2579
- 散金: 66
- 帖子: 252
- 在线: 450.2小时
- 虫号: 532712
- 注册: 2008-03-25
- 性别: GG
- 专业: 计算机网络
3楼2012-11-11 18:34:22
ftai
金虫 (著名写手)
- 应助: 19 (小学生)
- 金币: 7740.8
- 散金: 574
- 红花: 7
- 帖子: 1399
- 在线: 355.5小时
- 虫号: 2101685
- 注册: 2012-11-02
- 性别: GG
- 专业: 信息安全
4楼2012-11-11 18:50:02
chentianyu1
木虫 (小有名气)
- 应助: 67 (初中生)
- 金币: 2579
- 散金: 66
- 帖子: 252
- 在线: 450.2小时
- 虫号: 532712
- 注册: 2008-03-25
- 性别: GG
- 专业: 计算机网络
5楼2012-11-11 19:56:39
emmett08
金虫 (正式写手)
- 应助: 17 (小学生)
- 金币: 2958.8
- 散金: 2432
- 红花: 8
- 帖子: 426
- 在线: 368.6小时
- 虫号: 1945437
- 注册: 2012-08-19
- 性别: GG
- 专业: 模式识别
6楼2012-11-12 20:47:32
zhongyantao
铁虫 (著名写手)
- 应助: 3 (幼儿园)
- 金币: 810.8
- 散金: 80
- 红花: 3
- 帖子: 1062
- 在线: 275.7小时
- 虫号: 2052020
- 注册: 2012-10-09
- 专业: 信息安全
7楼2012-12-08 11:16:30
8楼2013-03-25 21:21:43