“人是社会关系的总和,人不能脱离社会而存在。”
物质世界是“普遍联系”和“永恒发展”的。
数学是现实世界中的“数量关系”和“空间形式”的科学。
真理越辩越明。
汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语!
Chinese is one of the six equally effective official languages of the United Nations.
Not to discriminate against Chinese, please!
[请教,讨论] P对NP(七):“形转换”与立体图、平面图
准确理解“立体图”、“NP完全问题”之间的关系,需要一定的专业知识:比较准确地了解 NP完全问题的特点。本文不再详细汇报。
一、平面图上的问题,也可以是 NP完全的
平面图上的问题,一定是 P类吗?
显然:不是。
这方面已有他人的理论性结果。
下面只举一个简单例子直观地说明一下:
考虑一个完全二叉树(perfect binary tree),如下图。
图1 一个 4层的完全二叉树(perfect binary tree)
https://media.geeksforgeeks.org/wp-content/uploads/20190514170438/Perfect-Binary-Tree1.png
显然,随层数(level)的增加,节点数按照指数方式增加。构造一个必须遍历所有节点才能得到答案的问题(人造问题):以层数或其等效变量为自变量,这样才能形成输入量的指数式增加。
尽管有穷完全二叉树是平面图,但也会形成 NP完全问题。
还有,将库拉托夫斯基图 K3,3 拆下一个边。这种“少一边的图 K3,3 ”的大量拼接,几乎也会形成指数的时间复杂性。当然还有“少一边的图 K5 ”的拼接。
图2 库拉托夫斯基图 K3,3 (左)和 K5(右)
https://encyclopediaofmath.org/wiki/Graph,_planar
类比:想想魏尔斯特拉斯在 1872年构造的那个“处处连续处处不可导函数”吧!“This function is continuous on the entire real line but does not have a finite derivative at any point.”,“although continuous, had no derivative at any point. ”
二、充分展开的立体图,往往关联 NP完全问题
对于包含足够多库拉托夫斯基图的非平面图,容易形成指数方式增加的搜索量(计算量)。
因此,平面图上的问题,不一定是 P。
非平面图上的问题,不一定是 NP完备的。
例如:风筝图。先构造一个直线图(大量的节点,但每个节点度数为2)。在这个直线图的一端,再接上一个库拉托夫斯基图。提醒:只接上一个库拉托夫斯基图。毫无疑问,这个“直线图 + 一个库拉托夫斯基图”的拼图是一个非平面图,但几乎不会形成指数时间的复杂性。
图3 “风筝图”的示意图。上图来自互联网,感谢。
下图中蓝色点表示直线图,风筝被一个 K5 图替换。
“形转换”是说:包含足够多库拉托夫斯基图的非平面图,容易形成指数方式增加的搜索量(计算量)。准确理解这点,需要比较准确地了解 NP完全问题的特点。不再进一步介绍。
“形转换”是一种带有“充分条件”推理特点的观点。不是“必要条件”。
三、无穷版本下的完全二叉树,不是平面图
这是我一个意外的发现。留念一下。似乎是一个真正的“创新”。
随便,再创新一个新术语“均匀地寂灭”(简称“均寂”),类似“热寂”。
“均匀地寂灭”,就是:
宇宙里面处处都一样。换言之,宇宙里面的不同局部之间,已经无法再彼此区分。
“热寂”,只是说“温度处处相等”。
“均寂”是说:宇宙里面什么都一样了。显然这是一种比化学元素、原子结构更深层次的基础状态起作用了。只要化学元素、原子结构存在,宇宙里面就会有“差别”。“幂集公理”实质上就有现实的对应物。“均寂”后,幂集公理就失去现实意义了。
参考资料:
[1] 2022-04-27,平面图/planar graph/朱小宇
https://www.zgbk.com/ecph/words?SiteID=1&ID=121796&Type=bkzyb&SubID=61829
[2] 2022-12-03,图论/graph theory/吴迪、李学良
https://www.zgbk.com/ecph/words?SiteID=1&ID=113666&Type=bkzyb&SubID=61823
[3] Graph, planar. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Graph,_planar
[4] Complete bipartite graph. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Graph,_bipartite
[5] Complete graph. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Complete_graph
[6] Kuratowski graph. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Kuratowski_graph
[7] Weisstein, Eric W. "Planar Graph." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/PlanarGraph.html
[8] Karl Theodor Wilhelm Weierstrass, MacTutor History of Mathematics archive
https://mathshistory.st-andrews.ac.uk/Biographies/Weierstrass/
[9] Non-differentiable function. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Non-differentiable_function
[10] Weisstein, Eric W. "Traveling Salesman Problem." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/TravelingSalesmanProblem.html
[11] Weisstein, Eric W. "Hamiltonian Graph." From MathWorld--A Wolfram Web Resource
https://mathworld.wolfram.com/HamiltonianGraph.html
[12] Weisstein, Eric W. "Hamiltonian Cycle." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/HamiltonianCycle.html
[13] Weisstein, Eric W. "Complete Graph." From MathWorld--A Wolfram Web Resource.
https://mathworld.wolfram.com/CompleteGraph.html
[14] Travelling salesman problem. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Travelling_salesman_problem
[15] Hamiltonian tour. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Hamiltonian_tour
Hamiltonian circuit, Hamiltonian cycle
See Graph circuit; Classical combinatorial problems.
[16] Graph circuit. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Graph_circuit
[17] NP. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/NP
[18] Complexity theory. Encyclopedia of Mathematics.
https://encyclopediaofmath.org/wiki/Complexity_theory
[19] Frank Harary. Graph Theory [M]. Massachusetts: Addison-Wesley, Reading, Mass. 1969.
一些近年的参考文献:
[1] Lance Fortnow. Fifty years of P vs. NP and the possibility of the impossible [J]. Communications of the ACM, 2022, 65(1): 76–85.
doi: 10.1145/3460351
[2] Jorge A. Ruiz-Vanoye, Ocotlán Díaz-Parra, Francisco Rafael Trejo-Macotela, Julio Cesar Ramos-Fernández. Editorial: P versus NP problem from formal languages theory view [J]. International Journal of Combinatorial Optimization Problems and Informatics, 2021, 12(1): 1-8. Jan-April 2021
https://webdesignwaterloo.net/all-p-problems-are-np-problesm-scholarly-articles
[3] Luciana S. Buriol, Celina Figueiredo, Mauricio G. C. Resende, Eduardo Uchoa. The guide to NP-completeness is 40 years old: an homage to David s. Johnson [J]. Pesquisa Operacional, 2020, 40: e236329, 1-11
doi: 10.1590/0101-7438.2020.040.00236329
https://www.scielo.br/j/pope/a/Cw4K8K374SySpJdNdx9kPLx/?lang=en
[4] Juraj Hromkoviˇc, Peter Rossmanith. What one has to know when attacking P vs. NP [J]. Journal of Computer and System Sciences, 2020, 107: 142-155. February 2020
doi: 10.1016/j.jcss.2019.06.004
https://www.sciencedirect.com/science/article/pii/S0022000019300558
[5] Igor L. Markov. Limits on fundamental limits to computation [J]. Nature, 2014, 512((7513): 147-154.
doi: 10.1038/nature13570
https://www.nature.com/articles/nature13570
[6] Lance Fortnow. The Status of the P Versus NP Problem [J]. Communications of the ACM, 2009, 52(9): 78-86.
doi: 10.1145/1562164.1562186
https://m-cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
发表的论文:
[1] A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): 446-449.
doi: 10.1007/s12209-011-1593-5
https://link.springer.com/article/10.1007/s12209-011-1593-5
[2] 第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374.
doi: 10.3969/j.issn.1673-5692.2011.04.009
https://d.wanfangdata.com.cn/periodical/dzkxjspl201104009
[3] 密码学与非确定型图灵机. 中国电子科学研究院学报, 2008, 3(6): 558-562.
http://qikan.cqvip.com/Qikan/Article/Detail?id=28856183&from=Qikan_Search_Index
[4] 人脑有多复杂?[J]. 百科知识, 1997, 7(总第216期): 39-40.
https://www.cnki.com.cn/Article/CJFDTotal-BKZS199707022.htm
[5] 人类智能模拟的“第2类数学(智能数学)”方法的哲学研究 [J]. 哲学研究, 1999, (4): 44-50.
https://www.cnki.com.cn/Article/CJFDTOTAL-ZXYJ199904005.htm
相关链接:
[1] 2023-07-07,[请教,讨论] P对NP(六):无穷化版本与连续统假设CH
https://blog.sciencenet.cn/blog-107667-1394463.html
[2] 2023-07-05,[讨论] P对NP(五):宇宙“热寂”之前,“幂集公理”不会有太大的毛病?
https://blog.sciencenet.cn/blog-107667-1394169.html
[3] 2023-07-04,[请教] P对NP(四):相关要点小结(问答式)
https://blog.sciencenet.cn/blog-107667-1394027.html
[4] 2023-06-29,[请教] P对NP(三):“NP完全性, NP-completeness”之后
https://blog.sciencenet.cn/blog-107667-1393466.html
[5] 2022-06-10,[请教] P对NP(二):结果的相对性与“1+3”种证明
https://blog.sciencenet.cn/blog-107667-1342404.html
[6] 2012-03-23,[请教] P对NP:请***教授等专家指教(一)
https://blog.sciencenet.cn/blog-107667-550859.html
[7] 2023-01-16,[搞笑?搞哭?汇集] 怎样判断“原创”和“诺贝尔奖成果”?
https://blog.sciencenet.cn/blog-107667-1372203.html
[8] 2015-05-22,The kernel of "P vs NP Problem": Axiom of power set!
https://blog.sciencenet.cn/blog-107667-892400.html
感谢您的指教!
感谢您指正以上任何错误!
感谢您提供更多的相关资料!
转载本文请联系原作者获取授权,同时请注明本文来自杨正瓴科学网博客。
链接地址:https://wap.sciencenet.cn/blog-107667-1394594.html?mobile=1
收藏