不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

NP是可判定的吗?- 集合与判断 精选

已有 5245 次阅读 2020-2-29 12:34 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记

目录

一,NP的形式化定义

二,集合与判断

三,人的判断

四,算法的判断

五,分析NP形式定义

六,质疑NP


NP的形式定义是用集合表达的,为了进一步理解NP,让我们回到对集合这个基本概念的理解上。


一,NP的形式化定义


NP存在二个被认为等价的定义:

Definition 1 : NP is the class of problems decidable by NDTM (NonDeterminisitic Turing Machine) in polynomial time. 

Definition 2 : NP is the class of problems verifiable by TM (Turing Machine) in polynomial time.


为了深入讨论,需要给出相应形式化定义。NP的形式化定义是借助于称之为“language(语言)的概念,将NP与集合联系,然后从“decision problem(判定问题)的角度定义NP


这是NP的形式化定义版本是Timothy Y. Chow采用Papadimitriou的书计算复杂性的第9章所得:

- R为二进制字符串上的关系; 即,让R为一组有序对(xy)的集合,其中xy是二进制字符串。 如果存在确定性图灵机在多项式时间内判定给定的(xy)是否在R中,我们则说R多项式可判定。如果 k >= 1 使得对于R中的所有(xy),y的长度(我们写为| y |)最大为| x | ^ k,则R多项式平衡

- 现在我们准备定义NP 当且仅当存在多项式可判定且多项式平衡的关系R,使得L = {x : (x,y)R中存在y}时,就说语言LNP中。


二,集合与判断


集合一般性指具有某种性质G(x)的对象的聚集整体,记A = {x G(x)}G(x)表达元素与集合的所属关系,即任给一个xG(x)=1,则xA中;G(x)=0,则x不在A中。

比如:偶数的集合,集合A = {x : mod(x, 2)=0}。给定整数20mod(20, 2)=0,故在A中;给定整数15mod(15, 2)/=0,故不在A中。


可以说,集合的定义是基于对所属关系G(x)判断,一个集合的定义有效性取决于对G(x)判断判断涉及判断的主体和客体。判断的客体指论域中的对象,比如:A = {x : mod(x, 2)=0},论域是所有的整数;判断的主体一般情况下指


Georg Cantor在最初给出的集合定义中明确表达了是集合定义中判断的主体:

集合是我们感知或思想的不同的对象的聚集,这些对象称为集合的元素。

A set is a gathering together into a whole of definite, distincts objects of our perception [Anschauung] or of our thought  - which are called elements of the set.


遗憾的是,在后来流行的集合定义中将我们感知或思想的省略了。当人借助机器来判断时,判断的主体就是算法,计算机理论中的PNP的定义正是这种情况。


三,集合与人的判断


一般情况下,一个集合的定义表达了人对某一事物确定性,在此情况下没有问题。但是,并不能保证任何一个看似成立的集合定义没有问题,比如罗素悖论:A={xxx},因对于A本身是否属于A的判断出现矛盾,故A的定义成为问题,由此引发第三次数学危机,直到提出公理集合论才暂时解决。


四,集合与算法的判断


在计算机理论中,集合的所属关系的判断借助与算法,如图灵所说:

- 一般过程(算法,图灵机)判定一个给定的整数n是否有性质G(n)[比如,Gn)可能表示’n是可满足的’’’n是一个可证明公式Godel的表达]


这样的定义首先就涉及到算法的存在性,这就是Entscheidungsproblem所讨论的核心问题。对此,图灵1936年的文章给出否定性的回答,判定问题不可判定

。。。,I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable.


所以,Entscheidungsproblem不是处理TM无法判定的语言,而是处理判定语言的TM的存在性。


五,NP与算法的判断


NP形式定义中涉及的集合RL,以SAT问题为例再来分析:

R = {(x,y) x is a satisfiable SAT instance and y is a satisfying assignment}

L = {x : (x,y) is in R for some y}


也就是说,R表达令一个SAT实例满足的所有赋值的集合;L表达所有可满足的SAT实例的集合。在认知上,RL的判定对应二个层次不同的问题。


比如:

- 实例f1 = (x1 x2 x3)(x1 x2 ¬x3)(¬x1 ¬x2   x3) (¬x1 x2 x3), f1 satisfiable,有四个解:x1 =0, x2=1, x3=1; x1 =0, x2=0, x3=1; x1 =1, x2=1, x3=1; x1 =1, x2=0, x3=1,故R = {(f,(0 1 1)), (f,(0 1 0)), (f,(1 1 1)), (f,(1 0 1))}

实例f2= x1 ¬x1, f2 unsatisfiable,无解, R为空集。

L = {f1, …}f1L中,但f2不在L中。


如此,RL集合的所属关系的判断就转移给算法了。


问:

1. R是可判定的吗?

答:YesR是可判定的,因为存在多项式时间算法判定R的所属关系。

2. L是可判定的吗?

答:YesL是可判定的,因为存在指数时间的穷举法判定判断L的所属关系。


六,质疑NP


然而,我们质疑NP形式定义,即“L是可判定的流行观点。


穷举法,即指数时间算法,基于“枚举”和“验证”,集合R的生成就是穷举法的结果。然而,枚举SAT解空间本身可枚举的性质,所以穷举法的本质就是“验证”,即多项式时间验证的算法


既然如此,从集合所属关系判断的角度,“L是可判定的就说明,L的判定与R的判定本质是一致的,换句话说,RL等价。此观点同时表达NP的形式定义和NP的非形式定义中。 


于是,在理论上,NP的定义暗含P=NP;然而在实践上,无论是直觉的认知还是具体问题的求解,P与NP是二个完全不同的问题,P/=NP。于是,理论与实践产生了矛盾!


所以,我们认为,需要重新审视NP的定义,从认知与逻辑的角度入手,追本溯源到图灵关于解决Entscheidungsproblem的工作,重新审视NPEntscheidungsproblem的关系。或许这才是解决P vs NP的根本路径,。。。


注:感谢与Timothy Y. Chow建设性的对话!





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

上一篇:图灵文章《论可计算数及其在判定问题上的应用》的第8章译文
下一篇:中国思想与先天综合判断 - 解构西方1
收藏 IP: 85.171.213.*| 热度|

3 杨正瓴 刘钢 黄永义

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 07:59

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部