应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 信息科学 » 程序算法 » 关于图论问题的NP完备性证明
81/1返回列表
查看: 1598  |  回复: 7
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

chentianyu1

木虫 (小有名气)

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

现在要证明一个图论问题是NP-Complete，是否只需证明它对于某些特殊拓扑的图（比如弦图、二部图）是NP-Complete的？如果答案是肯定的，请给出一个此类证明的例子。
个人感觉特殊拓扑的图是NP-Complete不能说明这个问题就是NP-Complete，否则我们平时用NP-Complete来判别问题的复杂程度就没意义了。
回复此楼

» 猜你喜欢
1楼 2012-11-06 15:27:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ftai

金虫 (著名写手)
　　《图论》和《组合（数学）图论》中的ＮＰ难题似乎比较多。
　　正在分析中：也许可以使用其中的一些ＮＰ难题用于设计非对称加密解密算法。类似于ＲＳＡ等，非对称加密解密算法主要是基于如：大数分解，离散对数，背包问题，以及椭圆曲线难题的。

　　一般有两种办法来证明某个问题是ＮＰ难的：
１、非确定性图灵机可验证的。
２、可映射归约到另一个ＮＰ难题。

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

chentianyu1

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

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

ftai

金虫 (著名写手)
　　从密码学的角度来看，ＮＰ＋组合图论＋密码算法，很值得研究。这是个应会出创新而有价值成果的方向。
赞一下 回复此楼
4楼2012-11-11 18:50:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chentianyu1

木虫 (小有名气)
引用回帖:
4楼: Originally posted by ftai at 2012-11-11 18:50:02
　　从密码学的角度来看，ＮＰ＋组合图论＋密码算法，很值得研究。这是个应会出创新而有价值成果的方向。

好吧，不过这还是没有回答我的问题。
赞一下 回复此楼
5楼2012-11-11 19:56:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

emmett08

金虫 (正式写手)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
chentianyu1: 金币+20, ★★★★★最佳答案 2012-12-07 21:15:20
不用证明其特殊拓扑的图是NPC的。并且巧合是很多是NPC问题，其二部图并不是NPC的，比如最大团问题是NPC 的，但是在二部图下并不是NPC的。
赞一下 回复此楼
6楼2012-11-12 20:47:32
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

zhongyantao

铁虫 (著名写手)
楼主，你的问题       “要证明一个图论问题是NP-Complete，是否只需证明它对于某些特殊拓扑的图（比如弦图、二部图）是NP-Complete的？”
的答案 是肯定的，在我看来。要举例的话，每个NP完全问题几乎都是这样的。

你要理解 一点就能 理解我的回答了：一个问题是np完全的，只需要该问题的一个实例(instance)是np完全的就够了。
赞一下(1人) 回复此楼
7楼2012-12-08 11:16:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dameng

银虫 (小有名气)
证明NPC的方法只有一个，就是把已知NPC问题在多项式时间内规约到你的问题。
赞一下 回复此楼
研究方向：数据库。主要面向图数据管理、图数据挖掘、社会网络等。目前正在关注动态图算法。
8楼2013-03-25 21:21:43
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 chentianyu1 的主题更新
81/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:42 by ZvyPK8n6Nfki
[找工作] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:34 by ZvyPK8n6Nfki
[找工作] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:28 by ZvyPK8n6Nfki
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:18 by ZvyPK8n6Nfki
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 tqUTOxClQUMF 2026-09-28 3/150 2026-09-28 23:46 by b8fCuTHqckEt
[考博] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +4 GDBe8tDZqE8z 2026-09-28 4/200 2026-09-28 23:19 by b8fCuTHqckEt
[考研] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 GDBe8tDZqE8z 2026-09-28 3/150 2026-09-28 23:12 by b8fCuTHqckEt
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 4/200 2026-09-28 22:55 by ez6fGg9abYaj
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +4 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 22:55 by ez6fGg9abYaj
[博后之家] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +4 IDs3scOF0tjC 2026-09-28 5/250 2026-09-28 22:45 by ez6fGg9abYaj
[有机交流] 同一个分子，一条来自文献，一条来自AI——不告诉你答案，你会选哪条？ +3 tianxiaoxian 2026-09-28 6/300 2026-09-28 22:44 by tianxiaoxian
[找工作] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 5/250 2026-09-28 22:32 by ez6fGg9abYaj
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 22:28 by ez6fGg9abYaj
[博后之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 3/150 2026-09-28 22:21 by ez6fGg9abYaj
[考博] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 6/300 2026-09-28 22:15 by ez6fGg9abYaj
[论文投稿] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 3/150 2026-09-28 19:08 by 9lS3ad5oOymn
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 18:51 by 9lS3ad5oOymn
[找工作] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +4 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 17:30 by ZYXdhzDAy9ZX
[教师之家] 某top大学教授说“能够在市场中兑现的能力才是真能力”无比同意！ +7 zju2000 2026-09-26 8/400 2026-09-28 16:42 by beefly
[教师之家] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 GDBe8tDZqE8z 2026-09-28 3/150 2026-09-28 15:32 by ZYXdhzDAy9ZX
信息提示
关闭
请填处理意见
关闭