含义/P对NP问题
“P类”、“NP类”、“更复杂的类”，是确定型Turing机DTM中的不同复杂性分类。这些分类是由不同问题的性质决定的，还是我们目前没有找到好的DTM解决方法形成的？这就是“P对NP”问题上。它的基本意思是： （1）P=NP：我们最终能够找到一些计算方法，使得NDTM能够快速解决的问题，在上也能够快速解决。快速的意思是“使用不超过输入字符串的多项式时间”。 （2）P≠NP：NP只能用NDTM快速解决，而不能用DTM快速解决。 假如P≠NP，关于NP类内部的结构，可以再分成3个区域：P、NPC和NPI。 NPC和是NP里“最难的”问题，因为任何NP中的问题可以在多项式时间内变换成为任何特定NPC（NP-完全问题，NP-completeness）的一个特例。这就是说，如果找到一个的快速解决方法，则所有的NP问题都可以快速解决了。NPI是NP中既不是P又不是NPC的问题类，如果P≠NP。 例如，密码学中的“素数分解”（大数分解和素性检测），就是一个NPC问题。假如P=NP，密码学的工作者必须改造的工作，实在是太多了！如果P=NP，则现有的大量密文都是容易解密的。
与密码学关系/P对NP问题
关于“P对NP”问题对密码学的影响，请看著名计算机科学家Stephen Cook（第一个NPC的提出者，1971年提出）2003年在“The importance of the P versus NP question”中的原始论述。Cook的基本看法是： 如果证明了P=NP，那么依据计算复杂性的密码术就是没有用途的。Internet（包含财政情报）的安全性是建立在这些假设上：的分解、DES (the Data Encryption Standard)的解密，不能用快速地解决。相反，不受P=NP的影响，可能解决的安全性问题。 如果证明了P≠NP，那么大素数的分解还是不是NPC的？证明RSA、DES等密码术的安全性比证明P?NP还困难。 不仅依据离散量运算的密码学受到“P对NP”问题的影响，而且依据连续量运算的密码学也受到实数环上的“P对NP”问题的影响。但人脑具有“”等非数学智能，如具有形象思维、动作思维、灵感直觉等，安全的密码学总是存在的。正常人右脑的非数学智能明显高于左脑的数学智能（Roger W. Sperry获得1981年诺贝尔奖The Nobel Prize in Physiology or Medicine的工作），因此未来更安全密码学的发展是没有止境的！
NP完全/P对NP问题
要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。
更难得问题/P对NP问题
虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找或最佳走法（在n乘n棋盘上）是指数时间完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定Presburger算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少22cn的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题。它们无法在任何给定时间内解决。
P≠NP论证/P对NP问题
如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个为几个因数的乘积，正是其求解过程的繁琐，才能杜绝的入侵。
而现在，美国惠普实验室的数学家围绕一个众所周知的NP问题进行论证，给出了P≠NP的答案。这就是布尔可满足性问题(Boolean Satisfiability Problem)，即询问一组逻辑陈述是否能同时成立或者互相矛盾。迪奥拉里卡声称，他已经证明，任何程序都无法迅速解答这个问题，因此，它不是一个P问题。 如果迪奥拉里卡的答案成立，说明P问题和NP问题是不同的两类问题，这也意味着计算机处理问题的能力有限，很多任务的复杂性从根本上来说也许是无法简化的。 对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的；但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题(Travelling Salesman Problem)，即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有计算机程序可以迅速给出这个答案。 迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可，但随后公布的论文终稿还将接受严格的审查。
万方数据期刊论文
大连教育学院学报
万方数据期刊论文
中国电子科学研究院学报
&|&相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
此词条还可添加&
编辑次数：11次
参与编辑人数：5位
最近更新时间： 17:38:39
认领可获得以下专属权利：
贡献光荣榜如图，四边形ABCO是矩形，点A（3，0），B（3，4），动点M、N分别从点O、B出发，都以每秒1个单位的速度运动，其中点M沿OA向终点A运动，点N沿BC向终点C运动。过点N作NP∥OC，交AC于点P，连结MP，已知动点运动了x秒，△MPA的面积为S。（1）求点P的坐标。（用含x的代数式表示）（2）写出S关于x的函数关系式，并求出S的最大值。（3）当△APM与△ACO相似时，点P的位置有几种情况？选择一种，并求出点P的坐标。（4）△PMA能否成为轴对称图形？如能，求出所有点P的坐标；如不能，说明理由。 
 - 跟谁学
跟谁学学生版:genshuixue_student精品好课等你领在线咨询下载客户端关注微信公众号
搜索你想学的科目、老师试试搜索吉安
跟谁学学生版:genshuixue_student精品好课等你领在线咨询下载客户端关注微信公众号&&&分类：如图，四边形ABCO是矩形，点A（3，0），B（3，4），动点M、N分别从点O、B出发，都以每秒1个单位的速度运动，其中点M沿OA向终点A运动，点N沿BC向终点C运动。过点N作NP∥OC，交AC于点P，连结MP，已知动点运动了x秒，△MPA的面积为S。（1）求点P的坐标。（用含x的代数式表示）（2）写出S关于x的函数关系式，并求出S的最大值。（3）当△APM与△ACO相似时，点P的位置有几种情况？选择一种，并求出点P的坐标。（4）△PMA能否成为轴对称图形？如能，求出所有点P的坐标；如不能，说明理由。 
如图，四边形ABCO是矩形，点A（3，0），B（3，4），动点M、N分别从点O、B出发，都以每秒1个单位的速度运动，其中点M沿OA向终点A运动，点N沿BC向终点C运动。过点N作NP∥OC，交AC于点P，连结MP，已知动点运动了x秒，△MPA的面积为S。（1）求点P的坐标。（用含x的代数式表示）（2）写出S关于x的函数关系式，并求出S的最大值。（3）当△APM与△ACO相似时，点P的位置有几种情况？选择一种，并求出点P的坐标。（4）△PMA能否成为轴对称图形？如能，求出所有点P的坐标；如不能，说明理由。 
科目:最佳答案
解： （1）延长NP交x轴于点D。DA=x，OD=3-x， ∴△PDA∽△COA，∴PD=x
∴P（3-x，x） （2）S=（3-x）·x=-x2+2x∴由顶点坐标公式可求顶点(，)
∴当x=，S最大值=（3）有三种情况当△APM∽△ACO时，3-x=x，∴x=，∴p(，2)（4）当PA=PM时, 3-x-x=x, ∴x=1 ∴P（2, )当PA=AM时，PA=x，∴3-x=x，∴x=，∴P（，）当PM=AM时，PM2=（3-2x）2+（x）2∴（3-2x）2+（x）2=（3-2x）2∴x=0或x=，∴P（3，0）或P（，） ∴P1（2, )，P2（，），P3（3，0），P4（，） 
解析
知识点:&&基础试题拔高试题热门知识点最新试题
关注我们官方微信关于跟谁学服务支持帮助中心& 记住密码
& “P对NP（P versus NP, P vs NP）”问题的描述、难度、可 ...
查看: 8951|回复: 13
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
本帖最后由 zlyang 于
17:43 编辑
“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案&&关键词：P对NP，P versus NP，P vs NP，the Millennium Problems，Clay Mathematics Institute
& & “The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.” [1], now it becomes a famous mathematical fundamental problem, though it was being a hard open problem in the field of computational complexity theory in the theoretical computer science since the early 1970’s [2]. “P vs NP Problem” or “P versus NP problem” becomes one of the most famous mathematical problems after the seven Millennium Problems released by Clay Mathematics Institute in 2000 [3]. Before this, in 1998, Steve Smale listed it as the third problem in his 18 great problems of the 21th century, i.e, “Problem 3: Does P=NP?” [4]. After this, in 2005, Science magazine listed it as the 19th question of its top 25 of the 125 big questions face scientific inquiry over the next quarter-century, i.e., “What are the limits of conventional computing?” [5].
& && &P≠NP is the mainstream perspective up to now. In 2002, a total of 100 people poll gave the following statistics [6]:
“ 1. 61 thought P≠NP.
2. 9 thought P=NP.
3. 4 thought that it is independent. While no particular axiom system was mentioned, I assume they think it is independent of ZFC.
4. 3 just stated that it is NOT independent of Primitive Recursive Arithmetic.
5. 1 said it would depend on the model.
6. 22 offered no opinion.”
About 6000 papers each year discuss the “NP-complete” or “P vs NP” [7], the recent reviews and papers can see [8-12], et al.
参考文献：
[1] COOK S. The P versus NP Problem, official problem description, [EB/OL]. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
[2] 中国大百科全书•电子学与计算机[M]. 北京: 中国大百科全书出版社, 1986.
Encyclopaedia of China • Electronics and computer [M]. Beijing: Encyclopaedia of China Publishing House, 1986. (in chinese)& &http://202.112.118.40:918/web/index.htm
[3] THE CLAY MATHEMATICS INSTITUTE. P vs NP Problem
[EB/OL]. http://www.claymath.org/millennium/P_vs_NP/.
[4] SMALE S. Mathematical problems for the next century [J]. Mathematical Intelligencer, ): 7-15.
[5] SEIFE C. What are the limits of conventional computing? [J]. Science, 31): 96.
[6] GASARCH W I. The P=?NP poll [J]. SIGACT News, ): 34-47.
[7] ALLENDER E. A status report on the P Versus NP question [J]. Advances in Computers, 7-147.
[8] FORTNOW L. The Status of the P versus NP Problem [J]. Communications of the ACM, ): 78-86.
[9] COOK S. The importance of the P versus NP question [J]. Journal of the ACM, 2003, (50)1: 27-29.
[10] GASSNER C. Oracles and relativizations of the P =? NP question for several structures [J]. Journal of Universal Computer Science, ): .
[11] MANEA F, MARGENSTERN M, MITRANA V, PEREZ-JIMENEZ MJ. A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors [J]. Theory of Computing Systems, ): 174-192.
[12] MUKUND M. NP-Completeness not the same as separating P from NP [J]. Communications of the ACM, ): 9-9.
[13] KURATOWSKI K, MOSTOWSKI A. Set theory [M]. Amsterdam: North-Holland Publishing Company, 1976.
[14] HAZEWINKEL M. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet “Mathematical encyclopaedia”[M]. Dordrecht: Kluwer Academic Publishers, 2001.&&《苏联数学百科全书》，http://eom.springer.de/
[15] HOPCROFT J E, MOTWANI R M, ULLMAN J D. Introduction to automata theory, languages, and computation (Third edition) [M]. New Jersey: Addison Wesley, 2006.
[16] GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1979.
[17] Nondeterministic Turing Machine [EB/OL]. /NondeterministicTuringMachine.html
[18] CHAITIN G J. Information-theoretic computational complexity [J]. IEEE Transactions on Information Theory, ): 10-15.
[19] 中国大百科全书•数学[M]. 北京: 中国大百科全书出版社, 1988.
Encyclopaedia of China • Mathematics [M]. Beijing: Encyclopaedia of China Publishing House, 1988. (in chinese)& &http://202.112.118.40:918/web/index.htm
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
“P对NP”问题的动态（参考资源）
本帖最后由 zlyang 于
17:15 编辑
WOEGINGER G J. The P-versus-NP page [EB/OL].
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
通常情况下，以下重复发表不属于一稿两(多)投：
本帖最后由 zlyang 于
22:33 编辑
通常情况下，以下重复发表不属于一稿两(多)投：
& & 1) 在专业学术会议上做过口头报告，或者以摘要或会议板报形式报道过的研究结果，但不包括以会议文集或类似出版物形式公开发表过的全文；
& & 2) 对首次发表的内容充实了x%以上新数据的学术论文；
& & 3) 有关学术会议或科学发现的新闻报道，但此类报道不应通过附加更多的资料或图表而使内容描述过于详尽；
& & 4) 重要会议的纪要、有关组织达成的共识性文件再次发表；
& & 5) 论文以不同或同一种文字在一种期刊的国际版本上再次发表；
& & 6) 在非英文的本国期刊上发表的属于重大发现的研究论文在国际英文学术期刊再次发表；
& & 7) 在内部资料发表后在公开刊物上再次发表。
您看在“重大问题研究”上，还需要注意哪些其它的“学术规范”？
谢谢您的指点！
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
其它相关资源、动态等，陆续在本条增加（长期更新中）
本帖最后由 zlyang 于
08:32 编辑
长期更新中
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
真傻对“P vs NP”的个人看法
本帖最后由 zlyang 于
13:36 编辑
实际上，“P对NP”不能被直接证明, 它是3个问题的合成：
① 对于NDTM，P=NP；(P = NP for a NDTM or NTM)
② 对于DTM，P≠NP；(P ≠NP for a DTM or TM)
③ “P对NP”具有独立性，如果不指明在那种计算机理论里进行研究。(The “P vs NP problem” can not be proved/decidable, without the necessary designating of a NTM or DTM.)
“对于DTM，P≠NP”的证明有3类：
（1）有穷形式下形转化的直接证明；
（2）无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”；
（3）概率形式、有穷形式下的直接证明。
欢迎您的指导与批评！谢谢！毛主席教导我们说：“科学是一门老老实实的学问，来不得半点马虎。”
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
真傻1995年报告的要点即将刊出，请您指点与批评！谢谢！
本帖最后由 zlyang 于
22:52 编辑
真傻1995年报告的要点，在《第二类计算机构想》扼要报道。
《第二类计算机构想》即将刊出，请您指点与批评！谢谢！
& && &&&真傻. 从NP结构到超级计算机分类理论[R]. 天津大学百年校庆研究生院学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会，1995年10月.
“对于DTM，P≠NP”的证明有3类：
（1）有穷形式下形转化的直接证明；
（2）无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”；&&
这2类在1995年报告中公布。
22:46 上传
“（3）概率形式、有穷形式下的直接证明。”计划近期投稿，请您指点！
（1）求真（2）真傻
最后登录&注册时间&威望0 &活跃度264274 ℃&金币70 枚&积分99&精华0&帖子30&主题2&
我看到很多美国人人在会议上发表的论文，又到期刊上发表。在美国，这显然是可以接受的。
距离创造美感
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
jiangxun 发表于
我看到很多美国人人在会议上发表的论文，又到期刊上发表。在美国，这显然是可以接受的。
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
真傻在“P对NP”及相关问题方面发表的论文
本帖最后由 zlyang 于
21:08 编辑
真傻在“P对NP”及相关问题方面发表的论文&&[1] 从NP结构到超级计算机分类理论[R]. 天津大学百年校庆研究生院学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会，1995年10月.
From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese)
[2] 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究[J]. 哲学研究, -50.
Philosophical resaarch on &the second mathematics (intelligent mathematics)& for simulations of human intelligence. Philosophical Resaarch, -50. (in Chinese)
[3] 密码学与非确定型图灵机[J]. 中国电子科学研究院学报, ): 558-562.
Cryptology and non-deterministic turing machine. Journal of China Academy of Electronics and Information Technology, ): 558-562. (in Chinese)
[4] 第二类计算机构想[J]. 中国电子科学研究院学报, ): 368-374.
Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, ): 368-374. (in Chinese)
[5] A non-canonical example to support that P is not equal to NP [J]. Transactions of Tianjin University, ): accepted.
支持P不等于NP的一个非规范例子（英文稿）。
拟投英文稿2个，正在写作。
真傻对“P对NP（P versus NP, P vs NP）”问题的思考，请看：
[1] Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）：
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
《P!=NP 的八卦传闻》：Mihalis Yannakakis
本帖最后由 zlyang 于
10:26 编辑
《P!=NP 的八卦传闻》
历史上已经有n多的人企图证明，包括很多正式发表的工作，最后发现都有错误。如果有人去考究就会发现斑斑血泪.有兴趣可以看下面网页:
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
比较有意思的是，其中有好几个中国人也在里头。更有趣的是有个大三的Ukraine学生声称证明了这个问题，他使用了“反证法”。
其实这个也是学术界博出位的好法子，跟娱乐圈闹绯闻有得一拼。不过科学允许失败，错了再来，又是英雄好汉一枚.
这个网页声称：到现在为止，唯一一篇发表在正式刊物上且被大家接受的文章是 Mihalis Yannakakis 的文章。不过不幸的是这篇文章没有解决这个问题，而只是告诉大家，对这个问题，有些方法是不行的。
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
“P vs NP 问题”的一句话回答
本帖最后由 zlyang 于
13:15 编辑
“P vs NP 问题”的一句话回答& &&&& && &&&在ZFC（Zermelo–Fraenkel set theory with the axiom of choice）中，由于“幂集公理 Axiom of power set”直接导致了“康托定理 Cantor theorem”。
& && &&&由于NDTM具有DTM幂集的能力，所以对于DTM，P≠NP。& && &&&根源在幂集公理Axiom of power set！& &
& &相关链接：[1] Cantor theorem
http://www.encyclopediaofmath.org/index.php/Cantor_theorem
[2] ZFC（Zermelo–Fraenkel set theory with the axiom of choice）
http://www.encyclopediaofmath.org/index.php/ZFC
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
本帖最后由 zlyang 于
11:38 编辑
吴健生《P!=NP 的八卦传闻》
Oded Goldreich的“既然他有能力证明这么伟大的猜想，他应该也有能力去说服大家看他的证明，去说服大家接受他的证明。”说法的另类解读：
做老板的可以不顾雇员的死活。
雇员必须有能力说服领导。
“领导就得骑马坐轿，老百姓想要公平？臭不要脸！”
《人民时评：“臭不要脸局长”的道歉有点假》
.cn/GB/.html
“行为人负有实施某种积极行为的特定的法律义务，并且能够实行而不实行的行为。”是典型的不作为犯罪。典型的举证责任倒置！做强盗有理！做顺民该死！
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
NPI 与“相变”
本帖最后由 zlyang 于
20:19 编辑
NPI 存在的话，可以否证“连续统假设”。
我倾向于认为存在 NPI：国内一些老师的仿真，表明 NPI 可能是存在的。可惜**人不相信我，不给我“好的工作站”和“不受干扰”的时间，进行 NPI 的有关仿真。
生活就是幽默。
在一些具体的“问题”里，由于各特定的实例有不同的“数量的结构”，而这些“数量的结构”中“数量的变化”会引起某些性质的质变，所以在 NPI 里（以及一些典型的NPC）里存在“相变”现象：计算时间随“某个量化指标的变化”出现明显的突变。
【高度对称的“约翰逊图”是他的算法方案里没有涵盖的唯一案例。】可能是这种“相变”里的另一种状态。
P. J. Cohen 和 K. Godel 已经证明“CH 独立于 ZF 或 ZFC”，所以找到 NPI 是有可能的。
而某些&&NPI 可能是处在“相变”边界的 NPC；一个真正的 P，不会出现“实质性的或真的”相变现象。
【“数量的结构”中“数量的变化”会引起某些性质的质变】的一个典型例子，就是从“平面图”到“非平面图”的突变：
Kuratowski 图 K5 或 K3,3。
[1] Graph, planar. Encyclopedia of Mathematics. URL: ,_planar&oldid=31832
[2] 库拉托夫斯基定理
/view/152234.htm
[3] Kuratowski's theorem
https://en.wikipedia.org/wiki/Kuratowski%27s_theorem
[4] Kuratowski Reduction Theorem
/KuratowskiReductionTheorem.html
[5] Kuratowski’s theorem
http://planetmath.org/KuratowskisTheorem
从 2SAT（P，不含Kuratowski 图 K5 或 K3,3）到 3SAT（NPC，可以包含同胚于 K3,3 的子图），就是随着“图中‘边的数量的变化’引起的质变（相变）”。
19:50 上传
杨正瓴. 第二类计算机构想 [J]. 中国电子科学研究院学报, ): 368-374.
19:50 上传
YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP [J]. Transactions of Tianjin University, ): 446-449.
（1）求真（2）真傻
最后登录&注册时间&威望8 &活跃度13353 ℃&金币5078 枚&积分5190&精华7&帖子872&主题142&
改错，抱歉！
本帖最后由 zlyang 于
20:23 编辑
【一个真正的 P，不会出现“实质性的或真的”相变现象。】
表述不够准确，应该为：
一个真正的 P，不会出现“实质性的或真的”相变现象。但可以存在“人为”的相变假象。
（1）求真（2）真傻
Powered by
Copyright &算法导论之P、NP、NPC问题
时间： 20:35:44
&&&& 阅读：698
&&&& 评论：
&&&& 收藏：0
标签：P、NP、NPC
& P问题：能够在多项式时间内解决的决策问题。
—举例: 图搜索问题、最短路径问题、最小生成树问题······
& NP问题：不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题。
—验证：给定一个问题的实例、证书（类似于证据），需要验证这个证书是这个问题的正确答案。
— 举例：汉密尔顿路径，实例为G=(V,E)，证书为顶点序列 {v0,v1,v2,v3,….,vk}，我们的目的是要验证这个证书就是这个问题的答案，验证方法为：先遍历一遍这个点序列，看看是不是每个点只出现一次，然后对于(vi,vi+1)是否为G的边，这样就能够验证这个点序列是不是汉密尔顿路径，很显然这个验证过程是多项式时间的，所以汉密尔顿路径是NP问题。
& NPC问题：目前不能用多项式时间解决的问题，但是我们还不能证明这个问题不能用多项式时间解决，我们这次的目标是研究这个问题。
—满足的两个条件：是一个NP问题 + 所有的NP问题可以在多项式时间内规约到它
—举例：3SAT、顶点覆盖、团、三维匹配、汉密尔顿回路、划分问题·······
& NP难问题：所有的NP问题可以在多项式时间归约到它，但它不一定是一个NP问题
& 归约(约化)的标准概念： 如果能找到这样一个变化法则，对程序A的任意一个输入，都能按这个法则变换成程序B的输入，使这两个程序的输出相同，那么我们说，问题A可归约为问题B
— 问题A可以约化到问题B的含义是，可以用解决B的解法来解决A，或者说A可以“变成”B。
—A可归约为B的直观含义：B的时间复杂度&=A的时间复杂度。也即，A比B简单。
P、NP、NPC、NP Hard问题的关系如下：
证明NPC问题
证明问题B是NPC问题的过程如下：
证明B是NP问题
知道一个已知的NPC问题A
证明A归约到B。
常见归约问题
1、独立集 —— 在图G = （V，E）中，如果顶点集合S?V中的任意两点之间都没有边，则称S是独立的。
—难点： 寻找最大独立集。
—目标： 装入尽可能多的顶点，要求边涉及到的边服从一些限制条件。
2、顶点覆盖 —— 给定图G = （V，E），顶点集合S?V，如果图中的每一条边至少有一个端点在S中，则称S是一个顶点覆盖。
—难点： 寻找最小顶点覆盖。
—目标： 用尽可能少的顶点覆盖图中的所有边。
3、集合覆盖 —— 试图用一组较小的集合覆盖一个任意的对象集合。
1、独立集问题——给定图G和数k，问是否包含大小至少为k的独立集？
2、顶点覆盖问题——给定图G和数k，问G是否包含大小至多为k的顶点覆盖？
3、集合覆盖问题——给定n个元素的集合U，U的子集S1，···，Sm以及数k，问在这些子集中有一组子集，它们的并等于整个U且至多包含k个子集吗？
4、集合包装问题——给定n个元素的集合U，U的子集S1，····，Sm以及数k，问在这些子集中至少有k个两两不相交吗？
5、SAT(可满足性问题)——给定bool变量集X={x1，···，xn}上的一组子句C1，···，Ck，问存在满足的真值赋值吗？
注意：每个子句均为析取子句(逻辑或∨)，最终结果为各个子句的合取(逻辑与∧)。
6、3-SAT(三元可满足性问题)——给定bool变量集X={x1，···，xn}上的一组子句C1，···，Ck，每个子句的长为3，问存在满足的真值赋值吗？
注意：同上。
设G=(V, E)是一个图，S?V，那么S是一个独立集当且仅当它的补V-S是一个顶点覆盖。
证明：首先，设S是一个独立集。考虑任一边e=(u,v)，因为S是独立集，u和v不可能同时在S中，所以u和v至少有一个在V-S中，即得任一边至少有一个端点在V-S中，所以V-S是一个顶点覆盖。
反过来，设V-S是一个顶点覆盖，考虑S中的任意两个顶点u、v，若它们间有一条边e，那么e的两个端点均不在V-S中，这与假设V-S是一个顶点覆盖矛盾。所以S中的任意两点均无连线，所以S是一个独立集。
常见归约问题
归约的一般思想(要点)：证明Y到X的归约，要用问题X中的分量构造“零件”来描写在问题Y中正在做的事
1、 独立集归约到顶点覆盖
证明：若有一个解顶点覆盖的黑盒子，那么通过问黑盒子G是否有大小至多为n-k的顶点覆盖，就能确定G是否有大小至少为k的独立集。
2、顶点覆盖归约到独立集
证明：若有一个可以解独立集的黑盒子，那么通过问黑盒子G是否有大小至少为n-k的独立集，就能确定G是否有大小至多为k的顶点覆盖。
3、顶点覆盖归约到集合覆盖
证明：若有一个可以解集合覆盖的黑盒子，考虑顶点覆盖的任一实例，给定图G=(V, E)和数k。
构造集合覆盖的一个实例，其基集U等于边E，对图G的每一个顶点i∈V，设Si?U为G中所有和点i相关联的边，把Si加入集合覆盖的实例中。
U能被集合S1,S2,···,Sn中的至多k个覆盖当且仅当G有大小至多为k的顶点覆盖。于是，给定顶点覆盖的实例，如上述的那样构造集合覆盖的实例，并把它输入黑盒子。回答yes当且仅当黑盒子回答yes。
4、独立集归约到集合包装
证明：若有一个解集合包装的黑盒子，考虑独立集的任一实例，给定图G=(V,E)和数k。
构造集合包装的一个实例，其基集U等于边E，对图G的每一个顶点i∈V，设Si?U为G中所有不和点i相关联的边，把Si加入集合包装的实例中。
U的子集S1，S2，···，Sn(实际是n个边集合)中至少k个两两不相交(即不存在相同边)当且仅当G有大小至少为k的独立集(此时k个顶点必不存在相连边)，于是，给定独立集的实例，如上述的那样构造集合包装的实例，并把它输入黑盒子。回答yes当且仅当黑盒子回答yes。
5、3-SAT归约到独立集
证明：设有一个解独立集的黑盒子，要解3-SAT的实例，实例由变量集X={x1，····，xn}和子句C1，····，Ck组成。
考虑3-SAT的方法是：必须从每一个子句中选择一个项，然后找一组真值赋值使得所有找出来的项都为1，从而满足所有的子句。因此，如果如果没有两个被选中的项冲突，那么就成功了。
具体归约：用独立集描述3-SAT实例。首先，构造图G=(V,E)，它由分成k个三角形的3k个顶点组成，如下图所示。对每一个子句i，构造3个顶点vi1，vi2，vi3。依据3-SAT实例子句在图中增加边描述冲突：在每一对标号对应冲突的项的顶点间添加一条边。
要证明原来的3-SAT是可满足的当且仅当构造出来的图G(依据3-SAT的实例子句构造)有大小至少为k的独立集。
&首先，若3-SAT是可满足的，那么构造出来的图G中的每个三角形至少包含一个标号的值为1的顶点。设S是每一个三角形中的一个这样的顶点组成的集合。设S不是一个独立集，则至少存在两个顶点u、v∈S间有一条边，则u、v一定是冲突(一个是1，另一个必是0)的，而S中的每个点值都为1，所以矛盾，所以假设不成立，即S是一个独立集。
&反过来，设图G有一个大小至少为k的独立集S。那么，当S的大小恰好为k，那么一定是由每个三角形的一个顶点组成，且S中的冲突顶点最多只能成单出现。所以显然可以设S中所有顶点对应的值全为1，且这些顶点每个对应于一个子句中选择的代表，所以此时对应的3-SAT实例存在真值赋值。
&&国之画&&&& &&&&chrome插件
版权所有 京ICP备号-2
迷上了代码！}