这里回应网友李红雨的博文（ http://blog.sciencenet.cn/home.php?mod=spaceuid=46717do=blogquickforward=1id=1018695 ），总结性的再谈我们为什么质疑 “NP是多项式复杂度的算法可验证的问题” 这一定义。 首先应注意到， 我们的讨论首重解读 流行的NP定义，其 目的是 辨析这些 定义 是否 捕捉到了“P vs NP”中“NP”的本质？所以，不能简单的、直接的以流行的NP定义作为 判断 的 标准 ，否则立即 就会 得出我们完全误读了流行NP定义的结论，从而无法将讨论进行下去。 在我们现在的讨论中同一术语NP有二个不同指称： 1，流行的NP定义：NP＝Nondeterministic Polynomial time（不确定性多项式时间），其中一个“简化版本”的定义就是“ NP是多项式复杂度的算法可验证的问题 ”。 2，我们的NP定义：NP＝Nondeterministic Problem（不确定性问题），这是我们通过从认知、逻辑和算法的角度解读NP流行观念后提出的。 对于“NP是多项式复杂度的算法可验证的问题” 这个 “简化版本”的 定义， 如果 “承诺”（注） ， 自然就会认为：“P属于NP，。。。P与NP的问题最大的猜想就是P是否能够等于NP，换句话来说，人们关心的是如果一个问题的结果能够用多项式复杂度的算法来验证，那么是否存在多项式算法来得出这个结果？”这是 网友李红雨在上述博文中对此定义进行的清晰 阐述 。 然而我们质疑这个定义，其中的一个重点就是问：虽然从计算求解的角度NP可以由多项式复杂度的算法来验证，但是“多项式复杂度的算法可验证”这一性质能否作为NP的本质来定义NP？即此性质能否帮助认知NP相对于 P 的本质特征？注意，“P vs NP”中的“vs（versus）”的本义就是“as opposed to，in contrast with”。 对此，我们的回答是：不能，因为P也是“多项式复杂度的算法可验证”的，进一步追究，就可看出：“多项式复杂度的算法可验证”不过是计算求解一个问题时所必须具备的“必要条件”而已，也就是说，当计算求解一个问题时，首先必须保证能有效的验证计算结果，但这与NP 相对于 P 的本质完全无关！ 正是为了帮助看清这一认知难点，我们借用“白马非马”的典故（公孙龙的“白马论”）： －曰：求马，黄、黑马皆可致；求白马，黄、黑马不可致。使白马乃马也，是所求一也。所求一者，白者不异马也。所求不异，如黄、黑马有可有不可，何也？可与不可，其相非，明。故黄、黑马一也，而可以应有马，而不可以应有白马，是白马之非马，审矣！ 如果是找“马”，找来黄马、黑马都可以；但如果是找“白马”，黄马、黑马就不可以了。若说“白马乃马”，是着眼于找“马”。若所找的仅仅是“马”，那么就不须区别“白马”与“马”了。若所找的是“马”，为什么有找来黄马、黑马可以与不可以的二种情形？可以与不可以，层次不同是很明显的。所以，黄马、黑马具有马的本质，符合“马”的这个大概念层次，但不符合“白马”这个二级概念层次，故白马与马在概念层次上不同，现在可以分析很清楚了！ 若放到“P vs NP”的语境中，将NP类比“白马”，P类比“色马（黄、黑马）”，“多项式复杂度的算法可验证”类比马的“形”，就是说，虽然“NP是多项式复杂度可验证的”（白马是马），但是却不能用此属性去定义NP（白马非马），否则无法辨析 相对于 P的 NP （ 求白马，黄、黑马不可致 ），故“NP类非多项式复杂度的算法可验证的问题类”！ 若进一步问： 我们为什么质疑“NP是多项式复杂度的算法可验证的问题”这一定义？就 是因为此定义不能引导人们认识P与NP的本质，正如说“白马是马”不能辨析“白马”与“色马（黄、黑马）”一样。 由此可见，“白马非马”沦为“诡辩”，“P vs NP”成为千禧年难题，事出有因： －“我希望在遥远的未来，当人们读到这四篇文章，可以帮助他们了解，在“P versus NP”还没得到解决的黑暗年代里人们的思想状态（I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved）。”－Hemaspaandra 注：“承诺” 一词出自奎因（Quine，1908－2000，美国哲学家、逻辑学家）的“本体论承诺”，这里可以理解为：如果你作出了一个命题，就承诺了这个命题所表达的问题是一个已经存在事实。
标签: NP”
