返回上一页 文章阅读 登录

周剑铭 柳渝:不确定性问题(NP)研究中的层次与中国传统逻辑

更新时间:2017-01-09 17:06:44
作者: 周剑铭   柳渝  

  

  

  

   周剑铭 柳渝(1,2)

  

   摘要:计算机和人工智能研究的一个最基本也是最困难的问题,就是算法与判断的基本性质及其关系。确定性问题(P)与可计算性概念是等价的,用术语表达就是P问题=P判定;但不确定性问题(NP)不能由可计算性定义,不确定性问题与确定性问题在判断的性质上完全不同,由于对这两个不同层次的问题在概念上的混淆和表达上的混乱,造成了计算机理论中一系列基本问题的困扰。借助于中国传统逻辑中的经典案例,我们把逻辑判断放在集合论的视野中进行分析,区分了P与NP的基本关系,把层次性引入到算法理论、逻辑学和一般认知领域中。中国传统逻辑可以给现代数理逻辑涉及自身的最困难的问题带来洞察的思想。

  

   Hierarchy in NP(Nondeterministic Problem) Research and Chinese Traditional

   Logic

   Abstract: One of the basic and difficultproblems in computer science and artificial intelligence is the nature of humanjudgement and that of machine decision as well as their relation. Thedeterministic problem (P) is consistent with the notion of computability, whichis expressed by the term P-problem = P-decision. However, the nondeterministicproblem (NP) can’t be defined by the computability; the nondeterministicproblem and thedeterministic problem are totally different in nature ofjudgment. Confoundingthese two problems and confusing their concept expressionat different levelsresult in perplexes for basic problems in computer theory.With the help ofclassical cases of Chinese traditional logic, we analyze thelogic judgment inthe field of set theory, distinguish the basic relationbetween P and NP, andintroduce the hierarchy into algorithm theory, logic andgeneral cognitionfield. Chinese traditional logic would bring insight into themost difficultproblems of modern mathematical logic involving itself.

  

   目录:

   一、算法与“判定问题”

   二、算法与确定性问题

   三、不确定性问题

   四、不确定性的消失和NP理论

   五、“白马非马”

   六、判断的层次

   七、大象无形

  

  

   “P versus NP”于2000年被美国克莱数学研究所指定为七个千禧年难题之一(可参见《紐約客》科普文章“P versus NP”[15]),此问题远远超出了引出这个问题的计算机理论领域,涉及到数学、数理逻辑、人工智能乃至哲学中的基本问题,所以Hemaspaandra在介绍Gasarch于2012年进行的第二次“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 people’s thoughts back in the dark ages when P versus NP had not yet beenresolved)。

  

   在当前的计算机理论中,P(Polynomial time,多项式时间)指计算机在多项式时间可求解的问题,具有可计算性本质;NP(Nondeterministic Polynomial time,不确定性多项式时间)[10]用来定义与确定性问题对立的不确定性问题。我们认为这个定义是对可计算性(确定性)与不确定性关系的误解,与此相关的理论观点及陈述不仅造成了在这个领域中工作者的普遍困扰,也是与此有关的逻辑、人工智能等领域隐含的困难的一个基本原因。

  

   我们的NP(Nondeterministic Problem,不确定性问题)理论[8],基于可计算性理论的基石,揭示了这些理论领域中“不确定性的消失”的现象,借助于中国传统逻辑中的经典案例,把逻辑判断放在集合论的视野中,理清“确定性”与“不确定性”,P与NP的性质和层次上的缠绕关系,在这个基础上进一步深入分析了算法与逻辑的层次性质以及逻辑判断的基本性质和内在层次,为相关领域的基本问题理论的研究提供一个更广阔的视野。

  

   一、算法与“判定问题”

  

   算法(algorithm)是一个古老的概念,是人类文明中经验和知识中原初的基本部份,今天屈指数数的儿童和背九九表的小学生,都是人类基本文明在个人早期成长中的返祖,计算机基本“算法”知识也是今天中学或大学教育中的必修课程。直觉地说,算法就是计算,按照严格的规则一步一步进行“计算”,比如欧几里德算法就是分解为基本的可执行的操作步骤,每个操作步骤都有确定的后继操作,因此算法常被直觉地认为就是“机械步骤”。

  

   在数学基本理论中,算法以递归函数的形式得到详细的研究,递归函数是可计算的,但这个函数的“可计算性(computability)”与直觉的“算法”概念之间,隐含有数学家称之为“能行可计算性(effectively calculability)”的一种性质。calculability源自拉丁语 calculus,指用于计数的小石子,因此calculability具有比computability更具体的操作性质,effectively calculability 译作“能行可计算性”,这个中文的“能行性”比英文的“有效性”更能表达“算法”这个概念中所隐含的机械操作性质。“能行性”表达了一种普遍性的解决问题的过程性能力,对这种普遍性的能力的考察被数学家隐含地表达出来,就是著名的希尔伯特第十问题[2](Given a diophantine equation with any number of unknownquantities and with rational integral numerical coefficients: to devise aprocess according to which it can be determined by a finite number ofoperations whether the equation is solvable in rational integers)。

  

   这个问题实际上包含了两个更一般性的内容:一、是否所有的数学问题都存在一般性的得到答案的算法?这实质是一种对问题(难度或复杂性)与解决问题的工具(数学函数或算法)能力之间的对应性的一种普遍性判断;二、算法的能行性如何体现?图灵以论文《论可计算数及其在判定问题上的应用》( On Computable Numbers, with an Application to

   theEntscheidungsproblem)[1]回答了这两个问题,前者就是“‘判定问题’不可判定”,后者就是著名的“图灵机”(circle-free)。对图灵的工作可以简要地说,图灵首先构造了一般算法的机器模型,回答了什么是算法能行性;在这个基础上,图灵的工作表明构造能计算所有数学函数的图灵机是不可能的。希尔伯特第十问题和图灵的解决通称“判定问题”(Entscheidungsproblem),它不仅是数学和逻辑学中的基本问题,而且具有更深刻的内容和更广泛的基础。

  

   算法与逻辑一直是现代计算机理论和技术的不可分割、分离的根基,在系统构架上是非常分明的,比如大家非常熟悉的软件和硬件,但这两者的关系在理论上却一直处于纠绕中,硬件和软件在一定的程度上是可以互相替代的,这种缠绕实际上来自人们对“判断”这个具有人类智能意义的相关意义概念的理解和分析,因此正在成为人工智能理论和人类大脑科学研究中最具基本性的问题,作为它的哲学意义,见已经开始成为“智能哲学”的主要内容。

  

   二、算法与确定性问题

  

   图灵的工作表明,一类数学问题可以通过确定性的方法得到确定的解答,即问题与相应的算法这两个方面具有某种同一性,这种同一性展开来说,就是问题的困难程度与解决问题的方法是相适应的,或者说,算法的能力与问题的困难程度是相适应的。这种对应性基于两者都具有确定性的本质,一方面,一个具有确定性性质的问题一定有确定性的答案;另一方面,这个确定性的答案可以通过确定性的机械步骤得到,图灵机就是这种机械步骤过程的机器化模型。这种“确定性”的性质或关系在理论上是以“多项式时间”(Polynomial Time)这个概念精确地表达的,“多项式”(polynomial)具有线性性质,这是相对“指数”(exponential)这种非线性性质来说的,因此“多项式时间”实际上就代表了一般性的线性性质。

  

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

(点击此处阅读下一页)
本文责编:zhenyu
发信站:爱思想(http://m.aisixiang.com)
本文链接:http://m.aisixiang.com/data/102771.html
文章来源:作者授权爱思想发布,转载请注明出处(http://www.aisixiang.com)。
收藏