《数学啄木鸟专栏》分享 http://blog.sciencenet.cn/u/wenqinghui 对错误的数学论点发表评论

博文

Zmn-0831 薛问天:证明出错,並未解决世纪悬奖的难题:P vs NP问题。评重庆理工大学学报。

已有 607 次阅读 2022-2-8 18:46 |个人分类:数学啄木鸟|系统分类:论文交流

Zmn-0831 薛问天:证明出错,並未解决世纪悬奖的难题:P vs NP问题。评重庆理工大学学报
【编者按。下面是薛问天先生的文章,是对《重庆理工大学学报》登载的温邦彦先生的文章《P/NP问题的答案是P≠NP》的评论。现在发布如下,供网友们共享。请大家关注并积极评论。另外本《专栏》重申,这里纯属学术讨论,所有发布的各种意见仅代表作者本人,不代表本《专栏》编辑部的意见。《专栏》中有些文章发扬了啄木鸟精神,对一些错误的观点和言论进行了说理的批评。但请大家注意,也有些有严重错误的文章在这里发布,就是为了引起和得到广大网友们的评论。不要以为在这里发布的文章都是正确无误的。】

 

证明出错,並未解决世纪悬奖的难题P vs NP问题

评重庆理工大学学报

 

薛问天

xuewentian2006@sina.cn

 

薛问天-s.jpgP同NP的关系问题(P vs NP)是这样的问题,问P类语言是否不等同与NP类语言(P≠NP?),即问: 由多项式时间运行的非确定的图灵机所接受的语言(NP类语言),是否不等同于能由多项式时间运行的确定的图灵机所接受(P类语言)。这是本世纪七大世纪难题之一 。

P同NP的关系问题涉及两个重要概念。一是确定的图灵机和非确定的图灵机,一是多项式运行时间和指数运行时间。亦即涉及到可计算性理论和复杂性理论,这是20世纪理论发展的重大成就。

本世纪初(2000年5月24日),美国麻省剑桥克莱数学研究所(The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) )在巴黎法兰西学院宣布,该机构设立了七个被称为“千僖年数学难题”巨奖,为每道难题悬赏奖金一百万美元。P同NP的关系问题就是其中之一。

克雷数学研究所还邀请有关研究领域的专家对每一个问题进行了较详细的详述。克雷数学研究所对“千年大奖问题”的解决与获奖作了严格规定。每一个“千年大奖问题”获得解决并不能立即得奖。任何解决答案必须在具有世界声誉的数学杂志上发表两年后且得到数学界的认可,才有可能由克雷数学研究所的科学顾问委员会审查决定是否值得获得一百万美元的大奖。

我国重庆理工大学学报(自然科学)2010年9月24卷第9期正式登载了温邦彦先生的文章《P/NP问题的答案是P≠NP》。

题目.jpg

-------------------------------------------------------------------------------------


难道温邦彦先生真正地解决了P同NP的关系问题(P vs NP),要获得世纪大奖了吗?

我将在本文指出,温邦彦先生的关于P≠NP定理的证明是个错误的证明。他根本得不出P≠NP的结论。这纯粹是重庆理工大学学报审稿不严,竟然毫无说明地登载这种错误的文章,确实是极不负责的有失文化水准的错误。

 

一,P同NP的基本概念。

P同NP的关系问题(P vs NP)是这样的问题,问P类语言是否不等同与NP类语言(P≠NP?),即问: 由多项式时间运行的非确定的图灵机所接受的语言(NP类语言),是否不等同于能由多项式时间运行的确定的图灵机所接受(P类语言)。

P同NP的关系问题涉及两个重要概念。一是确定的图灵机和非确定的图灵机,一是多项式运行时间和指数运行时间。

图灵机是英国数学家艾伦·麦席森·图灵(Alan Mathison Turing,1912-1954)在1936年的一篇论文中提出的计算机数学模型。简单说,图灵机有一条无穷长的带子,带子上有无穷个格子。每个格子里可以存储某有穷字母表∑={a1,a2,...,an}中的一个字符(包括空格字符)。在这条带子上连着一个可在带子上左右活动的读写头。每个时间拍,读写头对准着带子上一个格子。可以读和写这个格子里的字符,还可以左右移动它对准的格子。另外图灵机还有一个控制器,控制器每拍可以处于有穷个状态q0,q1,q2,...qm之一。每个图灵机都有有穷条控制规则(指令)。控制规则具有下述形式: a ,q→a,q’,t。其中a和a’是字符,q和q’是状态,t∈{R,L,N}。指令以a和q开始,它的意思是说该指令适合于,当读写头对准的格子中字符是a,而且控制器的状态是q时的情况,则该指令规定,在该拍要扏行′如下动作: 在格子中写字符a’,将控制状态转为q’。如果t是R,则右移一格,如果t是L,则左移一格,t是N,则不移动。

图灵机就这样工作。开始时把输入的字放在带子上,一个格子里放一个字符,从左到右顺序存放。然后将读写头对准第一个字符的格子,并且令控制状态为q0。接着就逐拍地按指令进行工作。直到遇到特殊的(停机)控制状态时,就终止扏行,停机。

如果在所有指令中,对每个a和q,以a和q开始的指令,只有一个,则图灵机每拍所执行的动作是唯一确定的,机器可确定地串行工作。称此类机器是确定的图灵机(DTM)如果在指令中,允许以a和q开始的指令,不止一个有多个,则图灵机就要在扏行中,相当于分成多个机器,来并行地扏行,进行并行的工作。称此类机器是非确定的图灵机(NTM)

如果存在一个多项式函数f(x)=b0xk+b1xk-1+...+bk-1x+bk,图灵机对每个输入字,当输入的字长是n时,在不多于f(n)个節拍(步)下即停机。我们就说图灵机是在多项式时间下完成的。

如果存在一个指数函数f(x)=bkx,当输入的字长是n时,图灵机在不多于f(n)个步下即停机。我们就说图灵机是在指数时间下完成的。

我们通常把某有穷字母表上的字(即字符串)的集合称为语言。如果一个字的集合A,当我们在断定任何字x是否属于此集合A时,可用一确定的图灵机(DTM),在多项式时间内完成断定x是否属于集合A。则称此集合A是P类语言。

如果一个字的集合A,当我们在断定任何字x是否属于此集合A时,可用一非确定的图灵机(NTM),在多项式时间内完成断定x是否属于A。则称此集合A是NP类语言。

由于DTM可以㸔作是NTM的特殊情况,即任何DTM都可以构造一个与其等价的NTM。所以显然有P⊆NP。

而悬而未解的悬赏奖金的难题。P同NP的关系问题就是问,P类语言是等同于还是不等同与NP类语言

现在NP习惯上有另一种等价的定义。

对于集A,如果x∈A的判定可以表示为存在一个字y,(这个字的长度不大于nk,其中n是x的长度,k是某自然数),使得R(x,y)成立。而R的成立可以由确定的图灵机(DTM)在多项式时间下确定。则称此A是NP类语言

 

二,温邦彦先生证明的错误。

大多数人认为问题的答案应该是P≠NP。但关键是要给出严格的证明。温邦彦先生在他的文中给出了证明。本文要指出的正是这个证明是错误的。我们来㸔他的证明。


--------------------------------------------------------------------

证明图1.jpg

证明图2-1.jpg




---------------------------------------------------------------------


显然证明中的第1句话的前半句【根据 NP 定义, 当且仅当, 存在多项式时间 NTM 程序的算题类,】是对的。但后半句说【得到 NP 类算题在 DTM 上目前还只能找到指数式算法, 否则不符合“仅当”。】则是含混不清的。首先,NP类算题只找到指数式算法,没找到多项式算法,没能证明P=NP,但不能因此就证明了P≠NP。把它作为证明P≠NP的正式根据,显然是不合适的。其次,说【否则不符合“仅当”】则是错误的。在NP定义中的【仅当】,并未排斥P=NP的可能性,认为【否则】,即P=NP,不符合NP的定义中的【仅当】,从而排斥了P=NP的可能,把此作为证明P≠NP的根据,显然是错误的。

要知道NP的定义中的【仅当】是指如果x∈NP,则必须对此x存在多项式时间NTM 程序。但是因为可证可以构造完全同DTM等价的NTM,所以如果对此x存在多项式时间 DTM 程序。就存在多项式时间NTM 程序。因而如果x∈P,则可以存在完全等价的多项式时间NTM 程序。使x∈NP。即P⊆NP。

接着我们看后面的证明。用的是反证法,假定P=NP,看能否推出矛盾来。

证明是这么说的【 即设,NP类中的任一算题可在现实的多项式时间得出正确的计算结论, 那么, NP 定义中神奇的假想在现实世界必须能够成真。 但是, 这是不可能的。

温先生所论证的并不是由P=NP引起什么矛盾,而是认为P是用的DTM,是【现实世界能够成真的】,而NP用是NTM,是【神奇的假想】。如果P=NP ,岂不【神奇的假想】变成了【现实世界能够成真的】,所以温先生认为【NP 定义中神奇的假想在现实世界必须能够成真。 但是, 这是不可能的。

也就是说温先生的证明是依据他的㸔法,P用的是DTM,是【现实世界能够成真的】计算,而NP用的是NTM,是【神奇的假想】,所以不可能P=NP,从而证明了P≠NP。

温先生说【笔者认为, 只要分清现实世界的理性与虚拟世界的神性, 采用逻辑法则即可解答。 解题的任务: 分析清楚定义的划分标准及必须符合的要求, 分析清楚算题分类定义 P 和 NP 的逻辑关系;解题的出路: 纠正对 P 和 NP 定义的不正确理解, 只要明白虚拟世界的神性不同于现实世界的理性, 就可立即得出 P≠ NP 的结论。

由于他的这个㸔法是错误的,所以他的证明是完全错误的。

 

三,温先生这个【客观世界】和【神奇假想】认识的错误。

温邦彦先生的这个认识本质上就是错的,他自己都不能自圆其说。例如他承认【NP 类算题在 DTM 上目前还只能找到指数式算法,】岂不是承认【神奇的假想】已经变成在DTM上的指数式算法这个【现实世界】的真正现实了吗?

实际上DTM和NTM都是理论上的计算机模型,不是客观现实的计算机。理论和客观现实不能是完全一样的。理论肯定要作一些抽象和理想化,不同于客观现实。不能把理论的抽象,理想化,看作是同现实对立的【神奇的假想】。实际上DTM也是理论上的抽象计算模型,不可能在客观现实完全实现。例如确定图灵机(DTM)中的无穷带子,在现实世界中就实现不了。温先生认为NP这种【假想的神奇能力在现实世界都不可能成真】的理由是【由于作为输入规模的自由变量 n 的增大不受限制】。其实这对P也是一样的,任何现实的机器都不可能如同DTM那样,接受长度不受限制的输入字。在现实世界中不可能存在无穷的带子,从而接受不了长度不受限制的输入字。可见确定图灵机(DTM)也是理论上的抽象计算模型,不可能在客观现实完全实现。

客观世界可以实现非确定图灵机(NTM)中的并行计算(如多CPU),但实现不了不加限制的无穷多并行计算。

DTM和NTM都是理论的计算模型,不是【客观世界】也都不是【神奇的假想。悬而未解的悬赏奖金的难题。P同NP的关系问题,P类语言是等同于还是不等同与NP类语言。这是一个数学理论问题。对于答案P=NP或P≠NP都要给出数学的证明,使用反证法就要推出理论上的矛盾,而不是说理论和现实的矛盾就能给出定理的证明。而这正是温邦彦先生定理证明错误的关键。

温邦彦先生说【操作必须明确范畴为现实世界或者虚拟世界, 现实世界必须采用现实能行的操作标准。 数学和逻辑还允许在虚拟世界中建立理论, 允许采用虚拟可行的操作标准。 但是, 现实世界和虚拟世界两者绝对不能混淆, 只有这样才能符合划分的目的。】而温先生把P㸔作是【客观现实能够成真】,而把NP看作是【神奇的假象】,认为P=NP,就是使虚拟变为现实,使【操咋标准】的【现实世界和虚拟世界两者】实现了【混淆】,认为这是【对 P 和 NP 定义的不正确理解】。显然这种观点是错误的。P和NP的定义在理论上是非常清楚的,定义中不存在任何理论上划分标准和操作标准的问题。这是理论模型之间的关系问题,根本不需要【做到现实世界的是非两分】。P等不等于NP,不是定义的问题,不是【现实世界的是非两分】问题,而是在理论上缺少相应的数学证明的问题,从而列为了世纪数学难题。只要证明了P=NP或P≠NP,有些相应的问题就会迎刃而解。

温先生所举的P1类是【定义:P1算题类,当且仅当, 现实已存在 (DTM 上已找到) 多项式算法的算题类。

显然不能以P1作为P的定义,因为P的定义是【可存在】,并不是【己找到】DTM多项式算法。而P1 所包括的都是在现在己找到】多项式算法的算题类。

温先生所举的“难解类” C是【是否具有多项式算法还不知道, 或不清楚, 或不确定的算题类。】 是在P/NP问题解决前时存在的类。如果有了证明后的答案,如果证明了P=NP,C的归属就完全清楚。显然C ⊆ P=NP。如果证明了P≠NP,显然可知C=C1∪C2,其中C1⊆P,C2⊄P,只知存在x∉P,C2≠Φ,但除C中的x外,并不一定知道,其它的元素哪些属于C1哪些属于C2,C1是否为Φ(空集),可能仍不知道。

 

四,温邦彦先生另一错误,定理2的错误。

温先生在文中还列出了定理2,这是他的又一错误。

定理 2 按现有的理解, P/NP 的证明任务没法完成。

这个定理2同定理1本身就是矛盾的。既然【P/NP 的证明任务没法完成】你怎么证明了【定理 1。 P/NP 问题的答案是 P≠ NP。

我们知道数学中的连续统假设的无法证明,是证明了它独立于集合论的ZFC公理系统。1938年哥德尔证明了连续统假设和ZFC公理系统不矛盾。1963年美国数学家保罗·寇恩证明连续假设和ZFC公理系统是彼此独立的。因此,连续统假设不能在ZFC公理系统内证明其正确性与否。

因而要证明P/NP问题的【证明任务没法完成】,必须证明此问题独立于ZFC公理系统。但是温邦彦先生并未作到这点,甚至就没有涉及集合论的公理系统。所以说他的证明从根本上是无效的。我们下面来具体分析温邦彦先生所给的证明。

-------------------------------------------------------------------


证明3.jpg

证明4-1.jpg

证明5.jpg





-----------------------------------------------


温先生分两段来分别证明P=NP和P≠NP没法证明

1),关于P≠NP他说【1),证明 P≠ NP 任务, 现有理论要求证明存在 x∈ NP 且 x∈ 乛P2, 这不可能完成。 如果证明存在某算题 x∈ NP 且 x∈乛 P1 , 那很容易做到, 例如 TSP 就 是。 但是, 学界会说: “ 现实不存在, 不等于, 不可能存在”, 要求 证明 NP 类中存在某算题 x 现实不可能存在多项式算法: x∈ NP 且 x∈乛 P2, 并说存在 C = 乛P 1 ∩ P2≠ Φ, 且 P1 ≠ P2。 但是, P2 的检验含义不明确, 没法完成 x∈ NP 且 x∈乛 P2的证明, 理由如下: 追问, 可能存在多项式算法的标准 P2 怎么检验? 没答。p 按理根据定义, 证得 x∈ P2 的证据只 能是 x∈ P1 , 那么证得 x∈ 乛P2的证据也该是 x∈ 乛P1 ,但是现有理论坚持不同意, 理由还是: “ 现实不存 在, 不等于不可能存在”, P1 ≠ P2。 那么, 只有等 C = 乛P1 ∩ P2类算题都验证完毕, 有了 C = Φ 时, 才会得到 P1 = P2 的证据, 从而接受 x∈乛 P1 的证据。 然而, 难解 C 类中任一算题也没法通过 x∈乛 P2的检 验。 因此, 按照现有理论的理解和要求, 永远也没法完成 x∈ NP 且 x∈ 乛P2的证明。

从这段文字中可以㸔出几个错误。

1 ,温说【学界会说: “ 现实不存在, 不等于, 不可能存在”,

实际上并不是这样,学界说的不是【现实不存在】,而是【现在还不知现实是否存在】【不等于不可能存在】。

这是对于P1和P2(即P)理解的错误,P1是现在现实已存在 ( DTM 上已找到) 多项式算法的算题类。】这个【已找到】指的是我们现在,在没有解决P/NP问题的新的证明以前,即在没有证明P=NP或P≠NP以前的时间【已找到】。在新的证明中找到的就不算在P1之中。而P2则是在现实中存在有多项式DTM程序,只不过其中有些我们现在还不知道而已。既使证明了P≠NP,存在有x∈NP,x∉P2,也仍然可能还不知道是否以后还会有新找到多项式DTM程序的算题类。因而温先生在这里断定【P1≠P2】是错误的。

另外,温说【按理根据定义, 证得 x∈ P2 的证据只能是 x∈ P1 ,】就完全是错误的。因为新证的x∈P2就不属于原先的P1。于是他所说的【 那么证得 x∈ 乛P2的证据也该是 x∈ 乛P1 】就是完全错误的。xP1不能作为xP2的证据,

没有了这个矛盾,他所说的【P2 的检验含义不明确, 没法完成 x∈ NP 且 x∈乛 P2的证明, 理由如下: 追问, 可能存在多项式算法的标准 P2 怎么检验? 没答。就不成立。P2 的检验含义非常明确,x∈P2就是存在多项式DTM程序。x∈乛P2,就是不存在多项式DTM程序。只要你证明了在NP中存在x∈乛P2,即x∉P2,就证明了P≠NP。

2,对C的理解错误,

按照温先生的定义,“ 难解类” C是【是否具有多项式算法还不知道, 或不清楚, 或不确定的算题类”。】证明P≠NP,并不一定要解决C的归属。只要证明C中有一个问题x∉P,既证明了P≠NP。因而温先生断定【C= 乛P1 P2】,是不对的,我们可能仍不知道全部C的归属,很可能还有C的元素不知其是否属于P(即P2)。即可能C=C1UC2,C1⊂P,C2⊈P。在P≠NP时只知C2≠Φ,但并不知是否C1≠Φ。仍不知是否P1=P2。

3,温先生说【只有等 C = 乛P1 ∩ P2类算题都验证完毕, 有了 C = Φ 时, 才会得到 P1 = P2 的证据, 从而接受 x∈乛 P1 的证据。】说得没有一点道理。

证明在C中只要存在一个x∈乛P2,(P2即P),就可证明P≠NP。当然只要证明存在一个x∉P,所有的NPC的元素也就都不属于P。但这同C中是否还有新证明存在多项式DTM程序的算题类无关,即仍可能有,从而P1≠P2,也可能没有,从而P1=P2。也就是说C1=乛P1∩P2等于或不等于Φ(空),这同P≠NP无任何逻辑关系。所以说温先生由此所得的结论【难解 C 类中任一算题也没法通过 x∈乛 P2的检验。 因此, 按照现有理论的理解和要求, 永远也没法完成 x∈ NP 且 x∈ 乛P2的证明。就是错误的,是没有任何根据的断语。

2),关于P=NP他说【2) 证明 P = NP 任务, 需要完成下面 2 项任务之一, 都不可能完成:① 要证 NP⊆ P , 即证虚拟可变成现实, 神奇 的假想能成真, 定理 1 已经证明这不可能完成!

我在前面已讲清楚,DTM和NTM都是理论的计算模型,不是【客观世界】也都不是【神奇的假想】。关于温先生讲的认为证明了P=NP就是【即证虚拟可变成现实, 神奇的假想能成真,】的定理1的错误,我在前面已讲清楚。

温说【② 要证, 存在 NPC 类某算题 x 存在多项式算法;x∈ NPC 且 x∈ P, 这也不可能完成。】当然这句话的错误,在于他所提供的【证据】是错误的。他说

当然, 这要提供证据, 就是要求找到 x∈ NPC 且 x∈ P1 。 注意, 现有理论承认, NP 类算题未找到多项式算法, 即( NP ⊆乛P1 ) ≠ Φ ( 否则就成了 P 类) , 根据 NPC 的定义可得 NPC NP, 于是, NPC ⊆ NP⊆ P1 , 因此, 存在 x∈ NPC 且 x∈ P1 , 必内含矛 盾。 这也是不可能完成的任务!

这段话的错误是逻辑的错误,只要证明在NPC中存在x∈P,即可证NP中全部元素属于P,即NP⊆P,从而证明P=NP。並不是要求x∈P1。我们知道在未证明P=NP的现在,P1中並未包含NPC中的任何元素。因而并不可能也沒有要求NP ⊆ P1。

另外,因为P1 ⊆ P ⊆ NP,显然(NP ⊆乛P1)是错的。说【(NP ⊆乛P1) ≠ Φ】就不对。因为温先生对【≠Φ】的解释是【是正确的】。在NP 类中有算题x现在尚未找到多项式算法,的表达应是(NP∩乛P1)≠Φ。所以并不存在NP ⊆ P1。因而並不存在温先生所说的NP ⊆ 乛P1和NP ⊆ P1的矛盾。所以说温先生的根据和结论【必内含矛 盾。 这也是不可能完成的任务!】是完全错误的。

既然所说的1)和2)两点都是错的,而且并没有证明P/NP问题独立于集合论的公理系统,自然定理2所说的【 P/NP 的证明任务没法完成。】就是错误的证明,而不能成立。

另外温先生所说的【现有理论隐含使用着 P 的两条标准 P1 和 P2, 其实, 它们的验证含义并没做出有效区分。 当你证明 P≠ NP 时, 要求你用标准 P2; 当你证明 P = NP, 要求你用标准 P1 。 这让你陷入两难境地, 始终没法完成证明。】的说法也是完全错误的。P只有一个标准,那就是P=P2。

五,结论

1),温邦彦先生提出的【P/NP问题的答案是P≠NP】並未得到证明,他的定理1的证明是错误的。因而这个世纪悬奖的难题,P同NP的关系问题並未解决,并未得到P≠NP这个答案。当然由此答案P≠NP所推出的一些断言,目前还不能确认为真。

2) P是否等同于NP的问题,就是对分类标准进行的数学证明。分类的标准明确关键是要在数学上进行严格的证明,而靠哲学上的【正确指导】。解决不了这个具体问题。而温邦彦提出的【定理 2 按现有的理解, P/NP 的证明任务没法完成。】也是错误的。因为要证明某问题的【证明任务无法完成】,必须证明该问题同集合论的公理系统是相互独立的。显然温先生并未涉及于此,而是作出了错误的推论。

3),既然温邦彦先生的证明是错误的,文中出现的很多观点和论据都是错误的,因他所归纳的他的所谓【主要创新点】就毫无意义。

另外,温邦彦先生的文中对罗素悖论、理发师悖论,微积分等悖论的论述,以及对数学基础理论及对图灵机停机的不可判定问题,哥德尔不完全性定理、 康托的实数集是不可列集定理的有关置疑,也有不少错误。由于温先生在文中並未对此展开具体专业的叙述,另一方面由于这同p/NP的主题无关,所以就不在此进行具体的评论。




返转到

   zmn-000文清慧:发扬啄木鸟精神-《数学啄木鸟专栏》开场白及目录

       











https://blog.sciencenet.cn/blog-755313-1324500.html

上一篇:Zmn-0830 吴文杰:回薛问天的《0827》《0823》
下一篇:Zmn-0832 侯小山:再谈实数可数定理和基数减少法 —回复《Zmn-0826》,及文清慧对此文的评语4。
收藏 IP: 111.19.46.*| 热度|

0

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

数据加载中...

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

GMT+8, 2022-8-19 13:20

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部