“人是社会关系的总和，人不能脱离社会而存在。”

物质世界是“普遍联系”和“永恒发展”的。

数学是现实世界中的“数量关系”和“空间形式”的科学。

真理越辩越明。

汉语是联合国官方正式使用的 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

https://www.geeksforgeeks.org/queries-to-find-the-maximum-xor-value-between-x-and-the-nodes-of-a-given-level-of-a-perfect-binary-tree/

   显然，随层数（level）的增加，节点数按照指数方式增加。构造一个必须遍历所有节点才能得到答案的问题（人造问题）：以层数或其等效变量为自变量，这样才能形成输入量的指数式增加。

   尽管有穷完全二叉树是平面图，但也会形成 NP完全问题。

   还有，将库拉托夫斯基图 K_3,3 拆下一个边。这种“少一边的图 K_3,3 ”的大量拼接，几乎也会形成指数的时间复杂性。当然还有“少一边的图 K₅ ”的拼接。

图2  库拉托夫斯基图 K_3,3 （左）和 K₅（右） 

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  “风筝图”的示意图。上图来自互联网，感谢。

下图中蓝色点表示直线图，风筝被一个 K₅ 图替换。

   “形转换”是说：包含足够多库拉托夫斯基图的非平面图，容易形成指数方式增加的搜索量（计算量）。准确理解这点，需要比较准确地了解 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

https://m-cacm.acm.org/magazines/2022/1/257448-fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/fulltext?mobile=true

[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

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！