[word doc]NP问题的答案是P≠NP

[word doc]NP问的答案是P≠NP NP问题的答案是P?NP 第24卷 Vo1.24 第9期 No.9 重庆理5-大学(自然科学) JournalofChongqingUniversityofTechnology(NaturalScience) 2010年9月 Sep.2010 问题的答案是尸??P 温邦彦 (天津商业大学经济逻辑创新研究中心,天津300134) 摘要:为了给出P/NP问题的答案,采用简单的逻辑法来证明,创造性地提出了定义 的划分必须符合逻辑的相容性,功能的合旨性(符合划分目的,结果”是”“非”分明),操作 的明确性(验证含义明确,范畴”虚”“实”明确)的3条5点要求.对P和NP的定义作了逻辑 的内涵和外延分析,由于NP定义中非确定性多项式算法所依赖的虚拟世界神奇假想,在现实 世界中不可能成真,所以在多项式时间内得不出算题计算的正确结论,从而也就得不出分类结 论(NPP),由此证明了P/NP问题的答案是P?NP.对”难解类”,”P标准的验证含义”,”P 是?尸的子集”作了辨析,证明:按照现有理解,P=NP和P?NP2种证明任务都没法完成.2 个定理正反双向证明了P#NP结论的正确.还对”梵塔算题属于尸类”提出了质疑,指出多项 式变换只能在NTM上实现,建议基于逻辑学,多元函数论和算法优化理论建立计算复杂性的算 题分类理论.对”停机问题”的不可判定结论提出了质疑,并且指出了对角线证法的错误. 关键词:P;?P;千禧年难题;计算复杂性;停机问题;对角线证法 中图分类号:O156文献标识码:A文章编号:1674—8425(2010)09—0108—19 AnswertoP,NPProblemisP?NP WENBang—yan (ResearchCenterforEconomicLogic,TianjinUniversityofCommerce,Tian jin300134,China) Abstract:InthispaperweanswertheP/NPproblem.usingasimplelogicalanal ysismethod.crea— tivelyproposingthattheclassificationstandardsmustmeetthefiverequireme ntsoflogicalcompatibili— ty,functionalcompliance(inlinewiththepurposeofclassification,andthebinaryresults,yesorno ontheobjectstobeclassified,arec/earanddefinite),andoperationaldefiniteness(unambiguous verificationofmeanings,andclearcategorizationofthevirtualworldandtherealworld).Basedon thelogicalanalysisofthePandNPdefinitions,thecorrectconclusionsofthecomputationalproblems cannotbededucedinthepolynomialtime,asthevirtualworldonwhichthenon?deterministicpoly— nomialalgorithmusedintheNPdefinitionreliesisassumptiveandmagic,andcannotcometruein therealworld.Thustheclassificationconclusion(?PisasubsetofP)of? Pclasseomputational 收稿日期:2010—03—21 作者简介:温邦彦(1947一),男,浙江瑞安永久机电学校校长,中国人民 大学现代逻辑研究所副所长,教授,主要从 事哲学,逻辑学,数学基础方面的研究,E-mail:wenbangy@gmail.com. 温邦彦P/NP问题的答案是P?NPl09 problemscannotbedrawn,andTheorem1isthereforeproved:theanswertotheP/NPDroblemis P?.Inthispaper,the”hardinc0mprehensmleclass”,”theverificationofPstandards”,and “PisasubsetofNP”aredifferentiatedandanalyzed,thusprovingtheTheorem2:UsingtheCUrrent— lyacceptedunderstandingsthetwoproofapproachesoftheP,NPproblemcanbecompleted.Thea— bovetwotheoremshaveprovedtheconclusionofP?NPinthepositiveandnegativemanner.This paperalsoquestionsthe”TowersofHanoicomputationalproblemsbelongingtoPclass”,pointsout thatthepolynomialtransformationcanonlyberealizedOiltheNTM,andproposestobuildaclassifi— cationtheoryofcomputationalproblemswithcomputationalcomplexitybased?onthelogic,muhivari— atefunctiontheoryandoptimizationtheoryofalgorithms;also,theconclusionthat”haltingproblemis undecidable”isquestioned,andtheerrorsofthediagonalproofarepointedoutaswel1. Keywords:P;NP;Millenniumproblems;Computationalcomplexity;Haltingproblem; Diagonalproof 1P/?P问题及解题出路 1.1P/NP问题的由来 1)P的定义——计算机的能力限度 ?问题可否汁算——停机问题.问题分为 “可计算”和”不可计算”.计算的基本功能就是 对一个问题给出”是”或”非”的判定,所以又可归 结为问题的”可判定”和”不可判定”.现有理论 认为:”停机问题”是不町计算或不可判定的,此类 之外的问题可计算或可判定.本研究把可计算 的问题称为”算题”,将对”停机问题”的不可判定 结论提出质疑. ?问题能否计算——P类定义.算题还分为 在现实有限时I1==I=J内”能计算”和”不能计算”.现 有理论用自然数n表述问题的规模,通过计算一 个算法完成所需要的基本步数t(n)来估计计算时 间.结论足:当t随n的增大不快于n的多项式函 数时,即t(n)?C/2”时(C是大于0的常数,n为固 定的有限自然数),则在现实有限时间内能完成计 算;当t(n)>cn”时,则在现实有限的时间内不能 完成计算.非多项式函数包括指数函数洲和n 增大更快的阶乘函数n!等. 定义:P类,当且仅当,存在多项式时间DTM 程序(确定性多项式时间算法)的算题类. ?算题能否划清——P类和难解类.P的定 义给出后,已找到多项式算法的算题划入了P类, 也称”易解类”.目前划入P类(本文用下划线记 述”非”)的非人为构造的算题只有梵塔算题(不 少专业书籍没有述及Jp类的例子,31).由于一个 算题可以有多种算法,大量现在还只找到指数式 算法的算题,例如旅行商算题(TSP)等,学界不敢 把它们划人P类,因为说不定将来还能找到多项 式算法呢!学界将其划人隐含”难解类”,但它又 不属于非”易解类”P类.那么,”难解类”到底该 如何解释呢?学界并没有说清楚. 2)?J的定义——神奇的计算能力 ??P的定义——非确定性多项式算法.有 些算题很难找到多项式时间的算法,如SAT算题, 即判定一个布尔代数式能否成真的算题,对于 这类算题,我们发现如果给了该算题的一个赋值 组,就可以在多项式时问内判断这个赋值组能否 满足公式.这种可以在多项式时间内验证一个解 是否正确的算题就被称为NP算题.继P的定义 之后,出于研究”难解类”算题的需要,学界又给出 了?P的定义. 定义:NP类,当且仅当,存在多项式时问NTM 程序(非确定性多项式时问算法)的算题类. 所述的非确定性多项式算法有”并行多值”和 “随机猜想”2种计算模型,分别有着在多项式时 间内”并算瞬完”和”随机猜中”的神奇能力.现 有理论还申明:这神奇能力的算法只能在虚拟的 非确定型图灵机(NTM)上实现,不能在现实的确 定型图灵机(DTM)上实现. 110重庆理工大学 ?NP的系列定义——试图对难解程度做出 精细的刻画.在NP类中又划出一种子类,称为 NP完全类,记作NPC,其特征在于:任何其他的 NP算题都可以多项式变换到其自身,一个NPC算 题J,据说它包含了NP中最难的那些算题.学界 还将”多项式变换”的概念扩展至”多项式时间图 灵归约”,得到NP难类,记作NP—Hard,多项式时 间图灵归约须在带”神喻”的计算机上才能实现, 神奇能力又升级了?.此外还有强?P,Co.NP 等,形成NP的系列分类,学界试图对算题难解的 程度做出精细的刻画j.但是,NP的系列定义并 没有真正解决什么实际问题,各类之间的逻辑关 系也始终说不清楚. 3)P/NP问题——计算复杂性的基础难题 有一点学界很清楚,尚未弄明白的最关键问 题是1971年S.A.Cook和L.Levin相互独立提出 的问题:P和NP这2种分类之间的关系,到底是 P=NP还是JP??P?这就是着名的P/NP问题. P/NP是计算机科学的核心问题之一,和其他历史 上有名的数学问题一样,它带给我们一个智力大 挑战.尤为重要的是,在与计算有关的学术领域 中,NP完全算题层出不穷,因此,P/NP是一个对 计算机和其它科学有全面影响力的问题. 如果P=NP,那么NP类算题都将现实能计 算.学界该做的事就是:千方百计去找到各种NP 算题的多项式时问算法,但是,互联网的安全问题 就会成为严重的挑战,因为破译互联网的RSA加 密系统属于NP算题],既然它也存在多项式算 法,就必须立即放弃这种加密系统,那么又该采用 什么样的有效安全措施呢? 如果P?NP,那么大量的NP类算题都将不 具有确定性多项式算法.学界就不该再把精力浪 费在NP系列的分类上了,应该赶紧去寻找各种 NP算题的最优近似算法,而对于互联网和其他需 要保密的系统之安全问题,则可以彻底放心了. 1.2P/NP的解题出路 1)解题的要求 做到怎样才算解决了这个难题呢? ?选定了答案,在P=NP或者P?NP这2 种答案中选择了一种. ?给出了证明,证明作上述选择的理由是正 确并且充分的,当然这要经得起时间的考验…. 有一点请注意,P/NP问题并没要求答案中给 出:可能存在多项式算法的明确条件,更没有要求 给出:所有的P类算题具体的多项式算法. 2)解题的任务 学界现在普遍认为l4,2种答案的证明之具体 任务是: ?若选P#NP,只要证明:存在某一NP类算 题永远不可能存在多项式算法. ?若选P=NP,只要证明:NP类所有的算题 都属于P类,因为学界已经公认P类所有的算题 都属于NP类.或者只要证明:NeC(即?尸完全) 类的某一算题存在多项式算法,因为,NPC类含于 ?P类,它具有一项特殊的性质,即NP类中任何其 他的算题都可以多项式变换到其自身L2j. 3)解题的出路 学界一直试图完成上述2项证明任务之一, 但经过了50年艰苦卓绝的努力,始终仍然没能找 到解决P/NP问题的有效出路.2000年初美国克 雷数学研究所(claymathematicsinstitute,简称 CMI)的科学顾问委员会选定了7个”千年大奖问 题”(millenniumprizeproblems),由于P/NP问题 的重要和艰巨,就成了其中之一_4J. 笔者认为,只要分清现实世界的理性与虚拟 世界的神性,采用逻辑法则即可解答.解题的任 务:分析清楚定义的划分标准及必须符合的要求, 分析清楚算题分类定义P和NP的逻辑关系;解题 的出路:纠正对P和NP定义的不正确理解,只要 明白虚拟世界的神性不同于现实世界的理性,就 可立即得出P??P的结论. 2定理1 定理1P/NP问题的答案是P#NP. 2.1定义的划分标准——逻辑内涵的分析 定义的划分标准,对子集的素质(子集中元素 温邦彦:P/?P问题的答案是P?NP 的性质)做出了规定.定义的划分标准还必须符 合一定的要求(即标准的标准),根据这些要求,便 可对分类的定义做出检验. 2.1.1划分标准的一般要求 笔者尝试归纳出划分标准的一般要求如下: 1)逻辑的相容性要求:?不含逻辑矛盾.矛 盾律作为逻辑法则,划分标准毫无疑意必须遵守, 论在现实世界还是在虚拟世界. 2)功能的合旨性要求:?符合划分目的;? 结果是非两分.划分标准的功能是为划分目的服 务的,自然就会要求划分标准必须符合划分的目 的.定义的划分功能则要求做y.1Jy~,J分结果的是非 阿分,若没做到,则标准就不符合功能要求. 3)操作的明确性要求:?验证含义明确;? 范畴虚实明确(虚拟可行或现实能行).操作要求 是对划分过程的要求,也是对标准执行的要求. 标准验证含义的明确是操作的前提,标准只有经 过检验之后才能被认可.检验必须提供证据,所 以必须保证标准的验证含义的明确,这样才能保 证划分结果的是非两分.操作必须明确范畴为现 实世界或者虚拟世界,现实世界必须采用现实能 行的操作标准.数学和逻辑还允许在虚拟世界中 建立理论,允许采用虚拟可行的操作标准.但是, 现实世界和虚拟世界两者绝对不能混淆,只有这 样才能符合划分的目的. 注意,划分的标准也是分层次的,这里的要求 仅仅针对基本的层次.在此基础卜,功能的合旨 性要求和操作的明确性要求还可以逐层细化. 2.1.2计算复杂性算题分类的划分标准 计算时间复杂性领域的算题分类定义的特殊 要求: ?划分日的:区分算题在现实有限时间内能 否完成计算,能否得出正确的计算结论.计算时 间复杂性的各种分类,基本目的都要解决实际问 题,区分算题在现实有限时问内能否完成计算,这 就要求首先应该得出算题计算的正确结论.如果 某种算法得出的计算结论是近似的结论,猜测的 结论,无关的结论,矛盾的结论,这些都不是正确 的计算结论,那么依赖这些算法就肯定得不到算 题分类的正确结论,当然也不符合划分的目的. ?划分对象:是算题,而划分标准是算法,规 定以耗时最短的算法作为划分的依据.如果划分 的对象就是算法,那就很简单,采用什么算法就属 于什么类.现在,划分的对象是算题,一个算题可 以有多种算法,现有理论已经规定以耗时最短的 算法作为戈0分的依据.由于定义必须符合”当 且仅当”的要求,若某算题类定义在DTM上只 有指数式算法,则具有耗时更短的多项式算法的 P类算题,就不该属于类.据此就可得到:(P X)=(f). ?基础标准:P类,算题分类的结论应该表 述清楚该类算题与P类的关系.已经确认现实世 界能完成计算的基础标准为:计算时间t为算题 规模n的多项式函数.所以,任何其他的划分标 准,包括NP的划分标准,都必须表述清楚:它与 P类标准的关系.(P)或(P)分别表示 类算题在现实有限(多项式)时问内能够或不能完 成计算.如果类中存在算题,i=1,2,( P)且(XP),那么划分标准与P独立无关, 不符合划分的目的;我们还可立即得到?P. 对于解决P/,vP问题特别需要引起重视的一 般要求: ?检验评价:算题分类的结论必须经检验评 价,分类结论和评价结论分属2个层次.例如, (NPP)是算题的分类结论,表示NP类中的所有 算题都具有多项式算法.对此需要检查NP划分 标准是否符合各项要求,然后做出评价.评价结 论为肯定的,则可以记作:(NPP)?;评价结 论为否定的,则记作:(NPP)=.分类结论 (NPP)或(NPP)和评价结论(?PP)= 或(NPP)?分属2个不同层次,后者必须经 过严格检验,必须通过证据审查才行. ?现实能行:现实世界中算题分类的正确结 论,其划分标准必须符合现实能行性.现实世界 的算题分类,必须明确为现实能行的操作标准,只 有在DTM机上操作才能够得到分类结论.如果 1l2重庆理X-大学 明确为虚拟可行的操作标准,例如NP类的划分, 在NTM上操作,那么只能得出虚拟世界的分类结 论l6,坨],但这并不能真正符合计算复杂性理论的 划分目的. 2.1.3对NP定义的划分标准之分析 1)作为NP划分标准的非确定性多项式算 法,符合逻辑相容性和操作明确性.作为NP划分 标准的非确定性多项式算法,本身没有矛盾,符合 逻辑的相容性.它的含义也是明确的,有并行多 值和随机猜想2种计算模型;而且范畴也已明确 在虚拟世界,明确只能在NTM上操作检验. 2)NP类算题,当且仅当,具有非确定性多项 式算法,表明目前在DTM上只有指数式算法.NP 类算题”当且仅当”在NTM上具有非确定性多项 式算法,即在虚拟世界中必须借助假想才具有多 项式算法.那么,不需要借助假想的在DTM上就 具有多项式算法的JP类算题,不符合”仅当”具有 非确定性多项式算法的NP定义,所以应有评价结 论:(P?P)?.另一方面,仅当在NTM上具 有非确定性多项式算法的NP类算题,现在DTM 上也只有指数式算法,否则它就属于P类了.所 以还有评价结论:(NPCP)?.本文对此还将 进一步讨论. 3)NP划分标准的功能合旨性必须正确理 解,它不能成为现实世界中算题的分类标准.NP 定义目的仍是区分算题在现实有限(多项式)时间 内能否完成计算.虽然这种非确定性多项式算法 所采用的并行多值和随机猜测的2种计算模型本 身是有用的,也具有发展潜力,但它们都不宜作为 在现实世界中算题分类的标准.请回答以下3个 问题: ?并行多值模型虽能提高运算速度,但它能 减少计算工作量,简化算法的函数式吗?并行多 值模型不能减少计算工作量,也不能简化算法的 函数式;虽然可以用来缩短计算时间,但也是有代 价的,它需要增加磁带和内存的数量,相当于用计 算复杂性的空间来换取时间.特别需要注意,并 行路数的增大只能在合理的限度之内.NP类算 题,目前在现实世界中只有指数式算法,也就是 t(n)?.;采用并行多值模型计算,欲在现实世界 中的t(n)?n”的时间内完成计算,而得到算题的 正确计算结论,那么并行的通路数就必须增为 的指数函数o,否则就没法在现实世界中完成指 数式/多项式的转换.但在现实世界中并行路数 增至受到了限制,这不可能,因为自由变量11,的 增大是不受限制的. ?随机猜想模型可很快求出近似解,但能以 此替代准确解而降低算题的要求吗?工业产品的 检验广泛采用随机抽检的,用它来部分替代 逐个全检的方法.但请注意,逐个全检得到的是 准确结论,而随机抽检得到的只能是近似结论. 随机抽检的算法比起逐个全检的算法确实减少了 计算工作量,缩短了计算时间,但是它所付出的代 价是:以近似结论来代替准确结论.NP定义中多 项式时间的验证,现实中只能是对抽检结论的验 证,而不该是对全检结论的验证.如果企图靠”随 机猜中”的假想能力来确保验证的是准确的全检 结论,那就必须在t(n)?n.的时间内完成a次 的猜测,而自变量n又不受限制,这在现实世界中 是不可能的. ?假想的计算机,虚拟的运算,这能作为现实 世界中算题的分类标准吗?非确定性多项式算法 的2种模型都只能在假想的NTM上虚拟实现,在 现实世界中这2种模型都不能在多项式时间内得 到算题计算的正确结论,从而就得不到算题分类 的正确结论.那么,在现实世界中给出这种非确 定性多项式算法的评价结论只能是(NPC尸) =. 2.2定理1的证明 定理1P/NP问题的答案是P#NP. 证明根据NP定义,当且仅当,存在多项式 时间NTM程序的算题类,得到NP类算题在DTM 上目前还只能找到指数式算法,否则不符合”仅 当”.假设P=NP,则必有(NPP):NP类中所 有算题都存在多项式时间DTM程序,即设,NP类 中的任一算题可在现实的多项式时间得出正确的 温邦彦:P/?P问题的答案是P?PiP113 计算结论,那么,定义中神奇的假想在现实世 界必须能够成真.但是,这是不可能的.理由:其 一 ,要在现实世界实现并行多值模型,并行通路的 条数必须增至n的指数条,否则,没法将n的指数 次串行计算转换成n的多项式次并行计算;其二, 要在现实世界实现随机猜想模型,必须在n的多 项式次随机猜中需要n的指数次计算的正确结 论,否则,只能得到近似的计算结论,并非正确的 计算结论.由于作为输入规模的自南变量n的增 大不受限制,这2种假想的神奇能力在现实tI}界 都不可能成真.那么,类中任一算题在现实世 界的多项式时间内都没法得到算题计算的正确结 论.所以,在现实世界中,在DTM上,算题分类的 评价就该是(NPP)=.对照P和定义目 的都希望划定在现实世界的有限时间内能够完成 计算的算题类,于是推翻假设,得到结论. 2.3关于定理1及其证明的说明 很多人对如此简单的证法会很不服气,谁还 不知道DTM?NTM呢?这就算证明了吗?!有人 认为,这不是数学的证明,只是哲学的思辨.还有 人说,P的定义也没做到在现实世界中的是非两 分,不然怎么会仔在”难解类”呢?不也可以把P 看成是虚拟世界的划分标准呀!笔者的答复是: 1)这确是哲学思辨的产物,但同时这也是逻 辑的证明.笔者根据3维5行辩证法,归纳出了 定义的划分标准必须满足的3条5点要求.任何 定义都必须接受检验评价.只有它的划分标准符 合上述要求,才是正确的,才叮以使用.由检验评 价所得出的逻辑判断,这本身就可以解决很多的 难题.P/?P问题的解答和证明,其实只用下面 这一句话就行了.P=NP的错,就错在混淆了现 实和虚拟”,违反了逻辑的同一律,不符合划 分目的. 2)对划分标准作检验评价就可解决难题的 例子.下面针对标准的5点要求分别举出5个例 子,都是着名的难题,长期未能解释清楚.解决它 们其实很容易,只要运用逻辑分析的方法,指出划 分标准不符合要求即可.这些例子为我们提供了 启示:P/NP问题也完全可以用十分简单的方法来 解决. ?罗素悖论(自身有矛盾的划分标准).对 集合做出是非分明的分类:不是自身元素的集合 A={aIa?a}和是自身元素的集合A={aIa? a.再将所有的集合组成全集A:{AIA?A}. 问:属于哪一类?若A?A,则A?A.无论如何 都矛盾,长期未能解释,故称悖论.其实,只用一 句话就排除了罗素悖论:划分标准A?A对于全集 A来说,已内含矛盾.不是自身元素的集合,却作 为元素又构成了全集.这条划分标准对于全集4, 就是谬论. ?”不能到达悖论”(目的不符合的划分标 准).从到B,必先到达AB的中点A;从.到 B,必先到达,B的中点A;依次类推,存在无限 多个中点,所以永远也到不了B.这里划分目的 应该是:能否到达曰点而不限任何运动方式.芝 诺仅仅提供一种运动方式,表现为公比为1/2的 无穷级数;但是他所设定的划分标准却是无限能 否穷竭.若能穷竭,就能到达;但由于无限在现实 中永有后继,不能穷竭,芝诺就得出了”到不了B 点”的结论.事实上,从中点出发只要继续行进同 样的路程,就能到达日点了.所以,芝诺的结论与 事实明显相悖,但是很多人对此一笑了之,学界也 长期没能给出令人信服的解释,故称悖论.在笔 者看来,这是个度量问题,与无穷并没有必然的关 系.芝诺却把它与无穷关联起来,设立了无穷能 否穷竭的划分标准.更重要的是,他以偏概全,就 得出不能到达的结论.他的这条划分标准不符合 “不限任何方式能否运动到达B点”的划分目的, 所以是不正确的. ?”飞矢不动”(是非不分明的划分标准). 这也是芝诺的一个悖论,它常被看成谬论,既在 “飞”又”不动”,岂不明显自相矛盾.其实,这里 的缺陷在于:没有指明运动的参照物,导致”动”和 “不动”的划分标准是非不分明.如果指明以”矢” 的自身作为参照物,那么不管它…I5I”还是”不 飞”,它都是不动的.”飞矢不动”也就成为设定以 l14重庆理工大学 自身为参照物的条件下的一句真理了. ?超限数悖论(范畴不明确的划分标准). 任何的基数(或序数,下同)都有大于自身的后继 基数,最大的无穷基数也有大于自身的后继基数, 但因为它已是最大,就出现”最大的基数大于自 身”的矛盾.这个悖论中比较大小的划分标准的 范畴虚实不明确,没有把现实世界和虚拟世界(理 想世界)区分开,也没有叙述清楚”无穷”这个概 念.”无穷”:在现实世界,表现为元素的永有后 继;在虚拟世界(理想世界),还表现为元素的一个 不漏.存在后继大于自身的关系,这在现实世界; 无穷的最大基数,这在虚拟世界.所以,在虚拟世 界中最大的基数已经没有后继了,也就不存在现 实世界中的”存在后继大于自身”的关系. 同样对于”微积分悖论”,贝克莱大主教质疑: 无穷小量一会儿大于0,一会儿等于0,岂不矛盾? 这也是由于微积分的极限理论中划分标准的范畴 虚实不明确造成的.无穷小量大于0,在现实世 界;无穷小量等于0,在虚拟世界(理想世界).只 要分清现实和虚拟,所谓的矛盾就可消解了.这 项质疑提出了一个亟待解决的问题,那就是当代 极限理论中范畴虚实的辨析. ?”白马非马”(含义不明确的划分标准). 这是古代中国的一道趣题,它也常被看成谬论,因 它与公认为正确的”白马是马”的论断相矛盾.其 实,这里的缺陷在于”非”的含义不明确.如果指 明”非”所对应的”不是”的含义为”不同于”,那么 “白马非马”无疑正确.由于”是”的含义还有”属 于”或”含于”,若把”非”理解成”不属于”或”不含 于”,那么”白马非马”就错了.由于”非”的验证 含义的不明确,是非的划分就不确定,这违反了同 一 律,划分标准也就不符合要求. 3)P的划分标准能否做到现实世界的是非两 分,还需深入辨析学界对P/NP问题的理解.P的 定义是现实世界的划分标准,这是非常明确的.P 的定义是否做到了在现实世界中的是非两分,这 取决于人们的理解和处理.提出这项质疑还是很 有见地的,有必要进一步辨析作者和现有理论对 P/问题的理解. 3定理2 定理2按现有的理解,P/NP的证明任务没 法完成. 3.1定义的划分结果——逻辑外延的分析 定义对它的上位概念做出划分,我们再来讨 论划分的结果,用集合论解释. 3.1.1一个标准的是非分明的划分 1)定义用一个标准将集合划分成”是”,”非” 2个子集.例如,定义P类算题,上位概念是算题, 划定其中的P类,剩下的就是P类(即非P).同 样,定义NP类算题,划定其中的NP类,剩下的就 是?P类(即非).注意,使用”非”,”不”等否 定词时,就要求做出明确的”是”,”非”两分. 2)定义须符合集合的质量标准:元素不假不 漏.这里的算题类是集合,类中的算题是集合的 元素,集合必须符合素质和素量的标准. 素质的标准:EP—?P.不具给定性 质的元素均在集外,即集内元素不假. 素量的标准:?P—?P.具给定性质 的元素均不在集外,即集外元素不漏. 根据集合的质量标准(素质和素量标准的合 称):P和P2个子集之问没有任何共同元素,否则 违反了矛盾律:PnP=.符号表示”空”或 “不存在”.集合都必须经过质量标准的检验;凡 是元素掺假的或遗漏的,都不该是集合J. 3.1.2两个标准的是非分明的划分(图1) 1)对一个集合做两个标准的是非分明的划 分,结果有3种可能. ?在一般情况下,会得到4分.既不重叠又 不遗漏的4个非空子集:n曰,AnB,ANB,AnB. ?在一定条件下,可成为3分.得到3个 子集. AnB=一一AnB=4一一(AB)条件下, A,和nB. nB=+__一AnB=B一一(BA)条件下, 温邦彦:P/,vP问题的答案是P#NPl15 ,和nB. ?在特别条件下,就只有2分.2个子集A 和,且A=B. 特别条件是:AnB=且4nB=+_-一 AnB=A且AnB=B一—+(B)且(BA),即 与B互相包含. AnB=,AnB=,ANB,且nB= 图l两个标准的是非分明划分的3种结果 2)由划分结果的子集数量,可得出2种分类 之问的关系.给出2个定义,可以从划分结果的 子集数量,推导出2个定义即2种分类之间的关 系.如果划分结果有4个子集,则2种分类不同, 并且存在咬合关系(也称2种划分独立).如果划 分结果有3个子集,则2种分类不同,并且存在包 含关系(也称2种划分关联).如果划分结果仅2 个子集,则2种分类相同,2种分类互相包含(也称 2种划分等价). 3.2P定义的理解和辨析 定义本该做到是非两分,但是在现实世界中 常常会出现做不到是非两分的现象,这有定义本 身的原因,也有对定义理解的原因. 3.2.1现实世界中P划分的2种处理 由于计算复杂性理论规定,划分对象是算题, 划分标准是算法,这就难以做到划分结果的是非 两分. 1)通常采用2种办法处理: ?P是现实能行的唯一标准,凡在DTM上未 找到多项式算法的算题,都划归于P类.这样处 理,P定义的检验标准就与设定标准完全一致,可 以做到是非两分.这时的”难解类”按字面理解就 该非”易解类”P类,因为P类也被称为”易解 类”.然而学界担心,可能会把一些本该属于类 的算题,因暂时没找到多项式算法,而错误划入了 P类.那么请问,什么时候才会发现错误呢?当 然是在DTM上找到了多项式算法之后.可见,这 样处理的定义P,严格讲求实证,符合划分目的, 也符合现实能行的操作要求.这类似于法律贯彻 的无罪推定原则,决不冤枉一个好人.只有证据 充足,才被判为罪犯;凡是证据不足的,都只能归 入非罪犯而无罪释放.凡在DTM上未找到多项 式算法的算题,都划归于P类.至于某些算题可 能存在一段时问的漏判,只要动态及时调整就行. 这也反映出人类认识的进步,完全可以解释和 接受. ?P设2条划分标准:DTM上的多项式算法, P现实已存在,P现实可存在.现有理论认为:算 题的多项式算法在理论上”可能存在”与否,是客 观的,确定的,不因人的认识和能力而改变;而”找 到”多项式算法却依赖于人的能力.例如TSP这 类算题,虽然未找到多项式算法,但仍然不轻易排 除它的可能存在,不把它划入P类,而把它称之为 “难解的算题”l3.现有理论没有明确给出”难 解类”的定义,但实际在使用着”难解类”这个概 念.注意,这不是非”易解类”P类;这一类又必须 与”已找到”多项式算法的P类和已确定”不可能 存在”多项式算法的P类区分开.现有理论就是 采用这种办法处理的,实际上这已经使用了两条 划分标准,增加了下面的定义. 定义:P算题类,当且仅当,现实已存在 (DTM上已找到)多项式算法的算题类. 这种处理办法把P的”存在”理解为”现实可 存在”,或”可找到”多项式算法的;又划分出了P 类,即为”现实已存在”或”已找到”多项式算法 的.”已找到”肯定含于”可找到”,亦即 (PlP)一一PlnP=Pl一一P1nP=.为了 清楚起见,还可记P=P,表示采用这第?种处理 办法. 这类似于有罪推定原则,绝不漏掉一个坏人. 犯罪是一种事实,找到罪犯则依赖于办案人的能 力,所以又将罪犯分为”已判决罪犯”和”未判决罪 116重庆理工大学 犯”. 2)注意上面2种理解的区别,而且,既不能混 为一谈,又不能”各取所需”.?中把P的”存在” 理解为”现实已存在”的意思,即P=P,以DTM 上”已找到”为标准.这是一条可检验的实证标 准,完全可以做到是非两分.?中,把P的”存 在”理解为”现实可存在”的意思,即P=P,以 DTM上”可找到”为标准.注意:这里的”可存在” 含义是确定的,不是”可能存在,也可能不存在”的 意思.这里的”可存在”并没有提出另外的检验证 据,仍以DTM上”找到”为标准,只是时限放宽了. 这2种处理办法中P,和都是现实标准. 本文定理1的证明依据在于,DTM上的现实标准 与NTM上的虚拟标准不同,所以结论的P?NP, 既包含P.#NP,也包含P:?NP,这2种处理方法 是各自独立的,应该分别讨论.不能既采用?又 采用?,来做同时的处理.绝不允许手握2条标 准,各取所需,专为己矛盾律.c作为集合,就只能是个空集:C?. ?若表示C类中算题属于P或属于P还不 确定,那么此含义表明划分未完成,违反了”定义 必须划定是非两子集”的规定,C类没做到元素的 不假不漏,C作为非空集合也不存在:C?. 肯定有人说,是否属于P还不能确定的那些 算题,才是难解的C类,它明明存在,怎么会空呢? 注意,这是说,在P只有一个划分标准的条件下, 难解类只存在于划分过程中,不可能存在于 结果. 2)若C的含义中P有2个划分标准,则C类 作为非空集,只能是C=P.nP.用和B2个标 准完成是非分明的划分,则只有AnB,AnB,AnB 和AnB共4个子集. ?设算题类A=存在多项式算法,B=存在 指数式算法.如果再设A=B,即指数式就是非 多项式,那就成了一个划分标准,有C?.即使 不设A=B,也该有C?.这是因为已经规定了 以耗时短的算法作为划分的依据,就有AnB=A 和nB=A,AnB=B,那就只剩下(An)?, 但它应表示:什么算法也不存在的不可判定型问 题.哪里还有什么难解类算题呢?2种情况都得: C?. ?设算题类A=P现实已存在多项式算 法,B=Pz现实可存在多项式算法,因”现实已存 在”且”不可能存在”不成立,P.nP=,那就成 了3分:P1=PlnP2,P=P1NP2和C=P1NP2. 3)若C含义中P有2个划分标准,而是否可 存在多项式算法,C类未判定,则C的验证含义不 明确.这样理解的难解类C,其中的算题c,i=1, 2,将会出现C?P且C?P2,这表明C与P是独 立的,必须给出”难解类”C的准确定义.但是现 有理论并没有另外定义”难解类”,还有,又该怎么 划定在尸2中的界线呢?如果把不可能存在多项 式算法的P:类中的算题划归于C类,犹如把”非 罪犯”纳入”犯罪嫌疑人”,本身就是一种失误.这 样的划分显然不合理,所以只能选定C=P.n P2). 结论:(C?)一(C:PnP). 所述的”难解类”c.就是”可找到而未找到现 实世界多项式算法的”算题类. 推论1c=PuP.用德.摩根定律直接证 得.非”难解类”就是,现实已存在多项式算法的, 或者,现实不可能存在多项式算法的算题类. 推论2P=P.uc.这表明P.和c都是JP的 子集.P不可能是c的子集,除非=.证明: 温邦彦:P/?P问题的答案是JP??P1l7 PlUC=PlU(PlnP)=(P.uP1)n (PuP)=/2GP=P,其中为全集. 3.2.3划分标准P,的验证含义不明确 特别提请注意,标准P的验证含义不明确, 不符合要求.注意: 1)?P,永远也无法完成证明.如欲证明某 个算题X?P,必须在DTM上找到多项式算法,等 同于提供的证据是?P.如欲证明?P,按 理,我们检验X?P和?P的标准应该一致,根 据定义证据也只能从DTM上取得.但是,现有理 论不认可X?P作为?P的证据,认为”现在不 存在”不等于”不可能存在”.这也就是说,当c? ,就意味着P?P,.这就使得证明者提供不了 证据.那么在什么情况下,才可以做到P.=P: 呢?只有C=时,这就需要把所有的C类算题 都检验完毕.难解C类算题大量存在,现在却连1 个算题的检验也通不过.所以,按照现有的理解, 永远也无法完成XEP,的证明. 2)”难解类”只能在划分过程中,不能在划分 结果里,它造成了标准不明确的困境.”难解