返回上一页 文章阅读 登录

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

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

  

   因此“多项式时间”并没有具体的时间的意义,不是指问题或计算机的时、空规模,而是指问题的规模和相对的计算能力之间的比较性质,即指问题的困难程度与机器的能力在增长性质上的对等性。这种问题的增长性质与机器能力之间的比较是由两者都是线性性质保证的:一方面,算法的确定性和解的确定性具有等价性;另一方面,具有确定性答案的问题是由能得到确定性的答案的算法定义的——这就是NP理论中基于“可计算性理论”由(能行可计算性)“算法”定义的“确定性”概念。

  

   三、不确定性问题

  

   很明显,“不确定性问题”是与“确定性问题”对应对立的,但与“确定性”这个概念完全不同,对“不确定性问题”的认识和理论上的定义充满了不确定性。

  

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

  

   图灵对希尔伯特第十问题并没有以Yes或No回答,就是说图灵并没有对希尔伯特第十问题提出一种一般性的判定方法,肯定(Yes)了希尔伯特第十问题,或者否定(No)了这种一般性判定方法的存在,因为否定了一般性的判定方法的存在——回答No也就是一种确定性的判断!图灵是以拒绝式的方式回答了希尔伯特第十问题,即著名的“‘判定问题’不可判定”,就是说“‘判定问题’不可判定”这个回答不是“存在(Yes)或不存在(No)的一个‘判定’”——存在(Yes)或不存在(No)都是对希尔伯特第十问题的一个确定性的回答,图灵却是拒绝——对希尔伯特第十问题“无法判定”,就是说图灵不是回答了希尔伯特所提出的第十问题的内容,而是拒绝了希尔伯特第十问题本身,即是对“判定‘判定问题’”这个更高层次否定。用这种层次分别上理解,可以明显地看出,“‘判定问题’不可判定”不是由机器产生的确定性的回答,而是图灵的工作所得到判定,是基于人的认知的判断能力产生的判定。

  

   我们可以用不同的术语区别地表达,希尔伯特第十问题的内容的是“判定”问题(Decision Problem),希尔伯特第十问题本身是“判断”问题(Judgment Problem)。图灵对希尔伯特第十问题拒绝式的回答包含了“希尔伯特第十问题”所隐含的更丰富、更深刻的内容和价值,因此统称“判定问题”(Entscheidungsproblem)。

  

   由于希尔伯特第十问题隐含了多个层次,所以希尔伯特第十问题和图灵的解答常常被误解并被进一步误导,由此产生很多的困惑并带来新的困难问题,其中最主要的一个就是所谓的“不可计算性”,表面看,“确定性”与“不确定性”是对应对立的,所以“可计算性”与“不可计算性”的对应对立就很自然,但这里面存在的层次上的缠绕所带来的误解和误导却是难以克服的。从对图灵工作的研究中可以看到,“可计算性”或“能行可计算性”这个概念对应的是“判断问题”而不是“不可计算性”,“不可计算性”相对应的倒是后来流行的“停机问题”(Halting Problem)(大体就是“不能停机的问题”),我们已经分析过了,这种误解的严重后果导致对“可计算性”这个概念的损害[16][17]。

  

   更广泛因而更严重的是对“不确定性问题”的误解,实际上造成了在理论上的认知错误,我们深入地研究了计算机理论中有关NP问题和NP完全性问题的来龙去脉,基于可计算性理论和对希尔伯特第十问题的研究以及对图灵的原论文解读,我们认为“不可计算性”这个术语在算法定义上不能成立,与“确定性问题(P问题)”对应的是“不确定性问题(NP)”,与“多项式时间(P)”或“(可计算性)算法”对应的是“确定性问题算法(P算法)”,而与“不确定性问题(NP)”对应的是应用非常广泛的最优近似算法,我们称之为NP—算法(NP-algorithm,“defined as the optimal algorithm to get the best fit approximative

   value of NP”)。

  

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

  

   对图灵工作的解读表明,正与“‘判定问题’不可判定”一样,“不可计算性”不能算法定义(自悖)。这种隐含的意义的误读产生了对图灵工作的另一个广泛的误解,这就是“停机问题(Halting

   Problem)”,这里的“停机”与“可计算的”意义相同,“停机问题”是以悖论方式证明的,“‘停机问题’不可判定”这样的悖论方式虽然“证明”了“‘停机问题’不可判定”,但却否定了“可计算性”这个基本概念本身,造成了基本理论和认知上的很多混乱,流行的NP问题和等价的“不确定性图灵机”(Nondeterministic Turing Machine, NDTM )、“停机问题”等都是对图灵工作的误读产生的。所以真正的NP不是机器的问题,而是人所面对的问题,因此“不确定性问题”的本质是人的问题。

  

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

  

   莫里斯·克莱因(Morris Kline)在“数学:确定性的丧失”一书中探讨了以确定性和精确性的内容为骄傲的数学发展过程中面临的自身的危机,伊利亚·普利高津(Llya Prigogine)的“确定性的终结——时间混沌与新自然法则”、费曼(Richard Phillips Feynman)的“科学的不确定性”等,都在一般科学理论中提出了“确定性”本身的问题,反映了现代人对知识和人类认知的全面反省,但另一方面,在代表现代科学技术的计算机理论领域中却存在着一种更为隐含和普遍性的实际困惑,就是我们称之为“不确定性的消失”的严重问题[14]。

  

   在算法和计算机理论中,确定性的问题就是有确定性算法解决的问题,但是确定性问题在我们所面对的事物中只是相对少数,相对的不确定性问题的性质一直是人类认知和知识领域中隐含得很深的一种困惑,计算机强大的解决问题的能力给人们带来了一种观念上的错觉:(所有的)不确定性问题总是可以确定性地解决的,用术语来说,就是P=NP,或者称之为“NP完全性”(NP-completeness),而且这种观点在理论上有系统性的表述并被普遍性地接受,但即使这样,人们并不能排除“不确定性问题”与“确定性问题”在本质上完全不同的直觉,即P≠NP,这两种观点的对立就是“P versus NP”这样一个“世纪难题”。

  

   我们认为,不确定性问题(Nondeterministic Problem, NP)的定义是这类问题不存在确定性算法。在大量的计算机求解的实践中,人们会有“不确定性问题总是可以由计算机解决的”这样的印象,但实际上人们总是事先约定或隐含地约定了将不确定性问题转化为最优近似求解的问题(也就是我们定义的NP-算法,NP-algorithm),而不是说,通过计算机求解,不确定性问题的不确定性本质消失了。“不确定性问题理论(NP理论)”通过揭示流行的NP问题类和等价的非确定型图灵机(NDTM)等概念中所隐含的“不确定性的消失”问题,以及对“不确定性”是如何从“不确定性问题”中消失的研究,揭示了P与NP的真正关系。

  

   与“确定性问题”由确定性算法(P算法)定义这种等价性不同,“不确定性问题”的本质是判断问题,而且不是所谓的“Yes or No的问题”,前文已指出Yes或No都是确定性的判定,“不确定性问题”是指“能否判定:对一切问题都能回答Yes or No?”,正如我们对图灵工作的解读,这个问题是不可判定的,所以NP的真正定义是与“判定问题”(Entscheidungsproblem)等价的。

  

   对不确定性问题的求解实际是“判断如何成为算法”的问题,正如大量实际问题的算法解决,这就是在事先约定对不确定性问题求解可以接受的條件下,将不确定性问题转变最优近似求解问题。在这个前提下,已经发明和成功地应用了各种最优近似求解的算法,就是“如何判定成为算法”的问题。“判断如何成为算法”与“如何判定成为算法”是对不确定性问题最优近似求解普遍方法,是本质的人、机关系。判断与判定对人和对机器具有不同的意义和性质,具有复杂纠缠的相互关系,这是由人和机器具有不同的本质决定的。“P  vs. NP”就是这种缠绕复杂性的集中表现,我们认为:“P≠NP, because they are disparate”。研究这两类问题的性质,特别是这两类问题的关系,就成为NP理论的主要内容。

  

   五、“白马非马”

  

   我们用中国传统逻辑的经典“白马非马”解析了流行的NP问题的两个定义中所隐含的层次上的混乱和对“停机问题”所存在问题的分析,理清了逻辑学和算法理论中一直存在两大困扰(NDTM 和“停机问题”),这些问题仅仅在算法理论或逻辑学中是无法解决的,因为这些问题与人的认知紧密相关,但又无法在一般的认知理论中解决。图灵工作的启示是把算法放在逻辑层次解决,因此把逻辑放在集合论层次研究,能够得到一种高层次的解决视角。

  

   逻辑学是西方思想的基石,逻辑学给中国传统学术带来的几乎是全新的视野,中国传统学术理论中只留下很少的与逻辑学有关的内容,但中国传统学术思想的“鲁棒性”(Robust)是无容置疑的,借助一个中国传统逻辑的经典案例“白马非马”,我们完全解析了算法与逻辑缠绕的困难。

  

   从现代集合论的观点看,“马”与“白马”是集合与子集合的关系,“马”(“形”或“象”)是马类不同于牛、羊等类的本质认知,“白马”则是在“马”这个大类中不同颜色马的子类。普通人(案例中的城门守兵)具有白马属于马类的常识认知而不自觉,所以认定“白马是马”(以枚举替代判断),智者公孙龙则从逻辑的严格上认为“马”与“白马”是不同的层次,坚持“白马非马”,以现代集合论的观点理解,“白马非马”具有逻辑层次上的不同。因此我们可以重新阐释“白马非马”。

  

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

   “白马非马”,可乎?

   曰:可。

   曰:何哉?

   曰:马者,所以命形也;白者所以命色也。命色者非命形也。故曰:“白马非马”。

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