# NP理论（5）：不确定性问题（NP）研究中的层次与中国传统逻辑 精选

＊＊＊＊＊＊

Hierarchy in NP（Nondeterministic Problem） Research and Chinese Traditional Logic

Abstract: One of the basic and difficult problems in computer science and artificial intelligence is the nature of human judgement and that of machine decision as well as their relation. The deterministic problem (P) is consistent with the notion of computability, which is expressedby the term P-problem = P-decision. However, the nondeterministic problem (NP) can’t be defined by the computability; the nondeterministic problem and the deterministic problem are totally different in nature of judgment. Confusing these two problems as well as their concept expression at different levels result in perplexes for basic problems in computer theory. With the help of classical cases of Chinese traditional logic, we analyze the logic judgment in the field of set theory, distinguish the basic relation between P and NP, and introduce the hierarchy into algorithm theory, logic and general cognition field. Chinese traditional logic would bring insight into the most difficult problems of modern mathematical logic involving itself.

P versus NP”于2000年被美国克莱数学研究所指定为七个千禧年难题之一（可参见《紐約客》科普文章“P versus NP[15]），此问题远远超出了引出这个问题的计算机理论领域，涉及到数学、数理逻辑、人工智能乃至哲学中的基本问题，所以Hemaspaandra在介绍Gasarch2012年进行的第二次“P versus NP”调查时说[9] ：我希望在遥远的未来，当人们读到这四篇文章，可以帮助他们了解，在“P versus NP”还没得到解决的黑暗年代里人们的思想状态（I hope that people in the distant future will look at these fourarticles to help get a sense of peoples thoughts back in the dark ages when P versus NP had not yet beenresolved）。

“多项式时间”用来表达算法或机器的能力与问题的困难程度是线性相适应的，即问题的规模增长与机器的能力之间是线性关系，这种性质保证了机器对要解决的问题能提供确定性的答案，这实际上也就是“算法”这个概念作为“能行可计算性”本质的机器化表达，因此，（能行可计算性）算法与图灵机是等价的，这就是“丘奇－图灵论题”所表达的意义。

“可计算性”这个概念是由算法定义的，或者说它们是同义的，但作为算法的“可计算性”的这种一般“能力”性质首先受到数学家的质疑，这就是由著名的希尔伯特第十问题所揭示的，希尔伯特第十问题大体上就是要求对存不存在能解决所有的数学问题的算法这样一个问题的判定，这个问题实际上包含了很多的层次，所以具有远超过这个问题的提出所具有广泛性和深刻性的意义。

“‘判定问题’不可判定”与真正的“不确定性问题（NP）”是等价的，即不存在P算法。虽然对“不确定性问题”不存在确定性算法，但人们总可以追求最优近似解（NP算法）

《公孙龙·白马论》原文摘录：

“白马非马”，可乎？

“停机问题”（Halting Problem）是计算机理论中流行的对“判定问题”（Entscheidungsproblem）的替代，在图灵的相关概念中，并没有“停机”这个术语，因为图灵机是一般意义上的算法模型，图灵只关心机器具有可计算性的本质，并不关心具体的计算机的时空能力，但从常识上说，“停机”就意味着得到确定性的答案，这就使“停机”实际上替代了严格的“可计算性”概念，从而使“停机问题”作为悖论形式隐含了对“可计算性”这个根本性概念的否定。“NP问题类”和“NP完全问题”就是由这些算法和逻辑层次上的误导产生的。

[1] A. M. Turing: On ComputabilityNumbers, with an Application to the Entscheidungsproblem. http://www.abelard.org/turpap2/tp2-ie.asp .

[2] David Hilbert: MathematicalProblems, http://aleph0.clarku.edu/~djoyce/hilbert/problems.html

[3] Martin D. Davis and Elaine J.Weyuker, Computability, Complexity, and Languages. Academic Pries, Inc. 1983.

[4] Michael Sipser. Introduction tothe Theory of Computation. PWS Publishing company.

[5] Michael R. Garey & David S.Johnson: Computers and Intractability, Bell Telephone Laboratories, Incorporated,1979.

[7] Stephen A. Cook, The P versus NPproblem, 2000. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf

[8] Zhou, Jian-Ming: Computability vs.Nondeterministic and P vs. NP, http://arxiv.org/abs/1305.4029 .

[9] Yu Li, What is NP? - Interpretation of a Chineseparadox white horse is not horse, http://arxiv.org/abs/1501.01906

[10] JianMing ZHOU,Yu LI, Whatis Cook’s theorem? http://arxiv.org/abs/1501.01910

[11] 周剑铭：算法理论与中国理性，网文。

[12] 周剑铭：“智能”哲学——人与人工智能，网文。

[13] 周剑铭，柳渝：机器与“学习”——寻找人工智能的幽灵，网文。

[14] 柳渝：不确定性的困惑与NP理论，http://blog.sciencenet.cn/u/liuyu2205

[15] 最深刻的数学问题http://blog.sciencenet.cn/blog-2322490-995211.html译文) The New Yorker, A Most Profound Math Problem http://www.newyorker.com/tech/elements/a-most-profound-math-problem（原文）

[16] “不停机”的circlefree——图灵1936年论文解读（3http://blog.sciencenet.cn/blog-2322490-993665.html

[17] NP理论的基本概念（2）：“判定问题”与“停机问题”http://blog.sciencenet.cn/blog-2322490-991454.html

https://wap.sciencenet.cn/blog-2322490-1016997.html

## 全部精选博文导读

GMT+8, 2024-5-21 10:11