如何评价姜新文老师提出的NP=P这篇文章？ 第1页

2020年8月4日更新：

我要解释一下“民科”二字。

错误的证明、错误的观点，这都很正常。如果一个人写了错误的证明，发表了有争议的观点，这完全不能说明这个人的学术素养有问题。甚至很多时候，需要争论，需要从一个错误的想法出发，才能得到正确的结果。

然而，一个人如果连基本的学术门槛都没入，却要解决顶级世界难题，写出的论文完全不通，不但如此，还时不时人格障碍般地说什么“很多人看过论文但找不出错误”，这就不正常了。这种人写的东西，鉴于其水平，并没有称得上学术的东西；别人捏着鼻子给他讲，他又自说自话地重复着自己的一套“理论”。这就叫“民科”。

我必须明确一点：姜新文是民科，而不是写了一篇有错误或者有争议的论文。这二者之间有天壤之别。我的纠错也只是好事者而已，千万不要以为，我纠了错，这就是一篇正常的有错误的论文，不是这样的。

姜的论文，和Deolalikar对P!=NP的错误证明，望月新一关于ABC猜想的证明，完全不是一个概念。后者是serious attempts，很轻易就得到了世界范围内顶级学者细致的检验。而姜的论文纯粹就是not even wrong，不会有人去给他查错，这也就是为什么他宣称“没有人找出错误”。

如果你不是搞TCS的，或许你会被姜的头衔迷惑，认为一个教授写的东西，哪怕是错的，也属于学术讨论的范畴。然而不是的，这种东西还不够格。

====================================

致所有想要让我给论文查错的人：

我在某答案下边说要查错需收100块钱，其实，这只不过是句戏言，我并不打算真的收钱。请站在我的观点为我想一想，我凭什么在这种毫无意义的“论文”上面浪费这么多时间？因此才有了收费之说。

但是现在我觉得澄清一下事实还是有意义的，因为最近几个月（或者几年）有不止一个人为这个所谓的“教授”辩护。这个人顶着“教授”的名分，毕竟和普通民科不同。而且，真的有一位网友说自己愿意出钱。不管真假，我都决定花时间读一下这篇神文，并且仔仔细细演算一番，把过程写下来，分文不取。这其实并不容易，连带看论文，在知乎上打公式，足足耗了我一个周末，别的什么都没干，再有下次，我可能真的要收精神损失费了。

这篇答案写得很长，但不要有畏惧心理，长度主要是需要验证的细节很多，而且写得极其详细，远远远远超过了一般的证明或者普通的writeup，这样不了解本专业的读者也应该可以读懂。

还有，我必须要匿名了（虽然本来也是假ID），实在不想在现实世界里被这种人纠缠。毕竟，知乎对我来说是一个娱乐网站，这是我为数不多地几次回答本专业的问题。

此答案分成以下几个部分：

一、为什么我说这篇论文毫无意义

二、论文概述

三、3SAT到MSP的归约（反例要用，我懒得看Hamiltonian circuit了，随便想了个归约）

四、反例和对论文细节的假设

五、反例证明（带进算法跑一跑）

六、附录：P vs NP的背景知识

一、为什么我说这篇论文毫无意义

我不知道有多少人会认真看后面的数学推导，所以干脆把这一部分容易读的放在开头。如果你不是搞理论计算机的，但是也做其他领域的研究，我想这一部分已经足够澄清黑白了。

1. DBLP上显示，他在发布P=NP的神文之前，没有发表过任何一篇论文。没有任何一篇。请大家自己去看：dblp: Xinwen Jiang。即便是在 P=NP 的神文上传arxiv之后，也仅发表过有限的几篇论文（网站上标CoRR abs的都不是发表，那是自己传到arxiv上去的。）
   即便是他后来发表的这几篇论文，也没有一个是有关理论计算机的会议。因为理论的论文和数学一样，作者都是按照姓氏字母顺序排的。而且这几个会议我一个都不认识，不知道是什么鬼。他发表的那几篇文章明显都是按照贡献大小排作者，他也从来没有一作。
   请问，我为什么相信一个完全没有科研经历的人可以搞定理论计算机和数学界最最著名的难题？理论计算机每年FOCS和STOC都分别各收百篇文章，注意是每年，还有SODA，ICALP，CCC各种各样的著名会议，他一篇都没发表过。可以负责任地说，这个世界难题就是他“研究”的第一个理论计算机的问题。
2. 有人说，个人资历不能说明问题，或许有扫地神僧呢。我们来看论文好了。这篇只有区区30几页。别的领域的朋友可能不了解，这种长度的证明相对于这种难度的问题来说，真的太短了，太不可能了，简直天方夜谭。几年前有人尝试证明P!=NP，那个证明有几百页，用了很高深的理论，在学术界和学术边缘都掀起了风浪，邮件争相传阅，有大佬在邮件里说"This appears to be a relatively serious claim"，最后还是被找出了错误。这位姜教授，没吃过猪肉还没见过猪跑吗？人家那是什么样的论文才被认定是serious attempt你看不出来吗？你的这种纯粹的初等方法乱套，凭什么让别人seriously对待？
   更神奇的是，姜“教授”这篇神文基本没有任何有价值参考文献，大部分引用都是他自己的、从未被承认过的“论文”，甚至是网页。这不奇怪，因为他的论文里的的确确没有用到任何已知的定理、理论。P vs NP的研究不说是汗牛充栋，也算是有成套成套的理论了，你真的什么工具都不用，就用最最初等、最最普通方法给做出来了？还只做了30页？
3. 再退一步，或许无数专业人士和天才都想错了呢，或许P vs NP真的就可以用很简单很初等的办法搞出来呢？我们来看看他的言论就好了。
   这是他的博客：XinwenJiang_新浪博客。诸位请上眼看一看，这不是民科是什么？这个人还有一点点学者的样子吗？人家给他公正的评价，他便要诉诸民族主义，说人家欺负他。没错，学术界是有很多不完全公平的地方，但是如果连“证明正确与否”这样“非是即否”的真理都可以因人而异，你相信吗？我认识很多国内学术界的老师朋友，他们都和国外学术界有着正常的互动。我本人也是国内走出来的。我郑重说一句：不公平的确有，圈子或许也存在，但没有你说的那种不公平。
   这个人处处在自吹自擂，说什么这篇神文引起了“专家”讨论。别的我不清楚，学术界基本的常识我是有的。倘若真的有任何一位专业认可你的玩意，让你成名只不过是给他的朋友们写一封邮件的事。不要说学界知名的专家，这件事连我都可以做到，随便找几个熟悉的大佬推荐一下就好。真实情况必然是没有任何主流学界的人认可这篇论文有价值（还不要求认可正确性）。
   还有一句非常搞笑的话：“发表了一批NP完全问题到MSP问题的归结”（2014年进展）。不明白这是干什么的读者可以看我这个答案最后的附录。MSP显然是NP完全的，我读神文的时候，自己证明这个用了2分钟；而既然是NP完全，那么任何一个问题就当然可以归结到MSP，这是理论计算机的基础知识，复杂性课的随堂练习内容，但是留作业都不合适，因为太简单了。你见过把练习题做出来发表的教授吗？
   他的博客实在太辣眼了，我就不多看了。

我们国家开放很晚，像理论计算机这样的学科无关国计民生，科研起步也非常非常晚，基础很薄弱，如果有年纪大的教授水平不高，知识体系不合格，这并不奇怪，甚至我们还更应该尊重他们，因为他们所经历的条件太恶劣的。

但是，这个人的言行已经超出了“知识体系”，而是已经触及到了我对于一个学者的修养和德行的底线。有很多人因为他是名牌大学的“教授”，就说他不是民科。我负责任的说，你们都错了。不要以身份判定一个人。这个人的科学素养完全就是民科水准，这是一个是非黑白的客观判定，而和他的身份无关。一个人有这样的言行，他就是一个民科。

他是“教授”，只能引起我对祖国国防事业深深地担忧，真的，我倒真希望他只是一个小学教师。我也曾经对所有顶着“老教授“头衔的人发自内心的尊重，不论我是否了解这个人，但姜新文的论文和博客真的让我三观崩坏了。

二、论文内容概述

首先，告诉所有想读此文的人两个好消息：第一，只看前五页就够了，算法就在前五页，后面都是算法的证明，而那个算法显然不可能是对的，你只要举个反例就行了。第二，这篇论文其实一点都不难（但是写得是真差，无谓的冗余操作真的很繁琐），完全没有什么真正的技术含量。

如果读者不了解P vs NP这个问题，我专门在在答案最后的附录里花时间写了一些介绍。但是，此答案仍然要求读者有基本的图论知识。

这篇论文定义了一个叫做MSP（Multistage graph Simple Path）的问题，然后给出了一个算法解决这个问题（当然算法肯定是错的）。Multistage graph的具体定义如下：

给一个分成很多“stage”的有向图，每个stage是一个点集，第一个stage和最后一个stage内都各只有一个点（分别记作S和D），每条有向边都只能是从一个stage到下一个。这个模型其实非常简单，我就不赘述了。特殊之处在于，图中每个点还要给一个label，这个label是一个边的集合。顶点v对应的集合为E(v)。

所谓MSP问题就是：

是否存在一条S到D的路径满足这样的条件：路径上每一点v，E(v)都包含了S到v这一段路径上所有的边？换言之，E(v)起了限定作用，即想要到达v只能走E(v)里的边。

那么这跟P vs NP有什么关系呢？有两步：

1. 需证明这个问题是NP-Complete，文中用Hamiltonian circuit给出了证明。这部分很简单，不管他的证明怎样（未读），结论都显然正确。
2. 文中大部分内容都是在讲MSP问题的一个多项式时间的算法。算法在第5页。对于每条边e，定义一个边集R(e)，里边包含了e到D之间有可能出现的边。算法就是按照几个固定的规则，不断的删减R(e)、E(v)之中肯定不可能的元素（比如说，E(v)里面如果有某条边从S连不到，显然这条边是可以去掉的）。就这样反复执行几个规则，直到所有R(e)、E(v)不再变化为止。如果此时E(D)非空，则说明存在从S到D的路径满足条件。

这两步合起来，就说明NP之中任何一个问题都有多项式解法（超级大新闻，千禧年大奖难题，千古留名，远超普通图灵奖，欧耶）。

不过不得不吐槽一下，这实在是一个没什么技术含量的想法。文中删减R(e)、E(v)的方法虽然复杂，但也仅仅是不断删减而已，除此之外这篇论文并没有什么新奇的想法（而且我相信这些东西看起来繁琐的原因是作者水平有问题，无法理清自己的思路，而不是它本身真的复杂）。

三、3SAT到MSP的归约（反例要用到）

我要说一下怎么从3SAT归约到MSP（文章证明了Hamiltonian Circuit可归约到MSP，但我太懒，3SAT更适合我）。不了解3SAT的请看答案的最后一部分，并且参照各种百科和网络资源。

归约很简单，大概如下图：

图中每条虚线都在某个只有一个点的stage之上，两条虚线之间夹有一个stage，其中有两个或者三个点（图的前半部分都是两个点，后半部分都是三个点）。从一条虚线到下一条虚线，有两条路或者三条路可走（前半部分两条，上或者下，后边部分三条，上中下）。

为了方便，引入几个定义：

1. 我们把虚线经过的顶点叫一个“端点“。
2. 相邻两个端点之间有两条或者三条路径，每条路径上的那个顶点叫一个“中点”。
3. 两条相邻虚线所夹的部分（4条边或者6条边）称作一个“小节”。

假设3SAT问题有n个变量 ，m个子句。我们下面对图中每条边，都“标注”上对某个变量的某个赋值 。这个标注与MSP里的label不一样，只是方便讨论的一个工具（MSP里的label 会通过标注定义出来）。具体如下：

1. 图的前半部分（后文把它称作“变量部分”）共有n个小节，分别对应变量 ，每个小节内有上、下两条路径。上面路径代表对应的变量取0，下面路径代表该变量取1。如上图所示，我们把第一组上方的 这两条边标注 ；而下方 这两条边标注 。类似的，第 个小节的四条边 上边分别标注 ，其中 。
2. 图的后半部分（后文把它称作“子句部分”）共有m个小节，分别对应每个子句，每个小节有上、中、下三条路径，对应子句中的三个变量。比如 这种，第一条路径的两条边标注 ，走这条路径代表 ；第二条路径的两条边标注 ，代表 ；第三条路径的两条边标注 ，代表 。和变量部分不同的是，这三条路径并不互相矛盾，并且选择某一条路径不代表其他路径上的标注不成立。如果子句被满足，则3条路径中至少有一条上面的标注是正确的。

这样，所有的边都有了标注。可以直观理解以下标注的意义，考虑一条从S到D的路径，如果路径上的边标注着对所有n个变量的赋值，可以重复，但不能矛盾（即不能同时有 和 ），那么这条路径就代表了对 的一组赋值。这样没有没有赋值就和有没有路径联系起来了。

接下来，我们定义 。

如果两条边 的标注是关于同一个变量但值不一样（即一个标 另一个标 ），我们就说这两条边“冲突”。

给一条边 和一个点 ，如果 是一个“中点”，并且与 相邻的前后两条边（它们的标注相同）都与 冲突，我们就说 和 “冲突”。注意，“端点”不和任何一条边冲突，只有“中点”才可能和边冲突。

对于每个顶点 ，我们定义 为所有可以连通到 的、与 不冲突的边组成的集合。（这里“连通”指的是普通图的连通意义，有边可以到达即可，不考虑MSP里 的限制。）

这样，我们就定义了一个multistage graph和每个点对应的 。 保证了只要找到一条满足 MSP 要求的路径，路径上的边的标注就不会有冲突。显然，3SAT 变量的一组赋值对应于图中“变量部分”的一条路径。3SAT 可满足当且仅当图中有一条S到D的路径符合 MSP 的条件。

四、反例和假设

既然算法声称解决了 MSP，那么必然也就解决了 3SAT。我们随便找一组“不可满足”的3SAT，比如下边这个：

总共3个变量， 个子句，分别是3个变量的8个子集中任找一个子集取反。这个 3SAT 显然是不可满足的，因为对于任何一组 的赋值（比如0,1,0），与之相反的子句（ ）是0。

根据上面的内容，可以构造出一个对应此3SAT的multistage graph。前面的“变量部分”分三个“小节”，分别对应 ，后面的“子句部分”分八个“小节”，分别对应八个子句。

我们来通过以下事实来复习一下之前的定义：

1. 对于每个“端点” ，没有和它冲突的边（ 包含所有可以连通到 的边）。
2. 对于“变量部分”的每个“中点” ， 同样包含所有可以连通到 的边（与 相邻的边不与 冲突，再往前则所有的标注都是其他变量）。
3. 对于“子句部分”的每个“中点” ， 前面的每个“小节”（可能是“变量部分”也能是“子句部分”）至多有一条路径（两条边）和 冲突（这说明 禁止掉了每“小节”里的至多一条路径、即两条边）。

这些只是为了检验理解，后面的部分如果用到这样的结论，不会直接引用而是会特别说明。

下面是两个关于论文细节的假设（文中没有说清楚）：

1. 第3页operator3的第(2)步，如果 和 相同，那么 包不包含 到 的路径呢？此时集合为空、路径退化为一点。我们假设是“包含”。
   因为如果不包含，则第5页算法的2.2步会出现大问题。那里用了一次operator3， 。按照operator3的第(2)步， 中所有与 相连的边（即 的情况）都要去除， 就成了孤点，这样算法对任何图的输出都是“不存在S到D符合条件的路径”。所以有此假设。
2. 第4页operator4在 （也就是 ）的情况下怎么办？此时，步骤(1)中的大括号（注意左括号‘{’和右括号'}'不在同一行）显然是空集（因为 不存在，即 左边没有边），因此所有 都要去除。这样 就成了孤点，对任何图，算法都一定会说“不存在从S到D符合条件的路径”。
   因此，我们假设operator4不会用在 的边上。换言之，当 （即 时）我们假设 。

有非本专业的读者可能会问这个反例是怎么想到的？这个反例其实非常非常自然，也非常非常必然。既然声称解决了MSP，那就必然也解决了3SAT，我随便拿一个3SAT按照这个算法跑跑好了。这个3SAT已经是在满足“每个子句都有3个不同变量且不可满足”的条件下最小的了，结果算法连最小的都通不过（！！！）。事实上，哪怕是随机找一个非特殊情况的3SAT（大多数子句都有3个变量），这种只用简单迭代的算法都是不可能通过的。该“教授”博客中提到通过了很多测试，100%有问题。

五、反例证明

我们来说明图中的算法会认为该图中存在S到D、且符合 约束的路径。

这涉及到了论文的细节，建议读一下论文的前5页，一些繁琐的内容大致看一下即可，大致了解框架就可以了。我们下面（用引理的形式）来说明operator2的结果是什么，并验证operator3和operator4都是完全无效的。

引理一：如果用论文第3页的operator2来初始化所有的 ，那么 的初始值是：从 出发可以连通到的、不与 “冲突”的所有的边组成的集合。（这里的“连通”指普通图的连通，不考虑MSP中 的限制。）

证明：第3页operator2有两步计算。

第一步 ES 其实就是与 之后不冲突的边的集合：对于式子中的 这条边， 之中必有一个“端点”一个“中点”，我们知道 是否与 冲突等价于 中的“中点”是否与 冲突，而“端点”不会和任何边冲突，故 与 不冲突当且仅当 。

第二步取 就是 可以连通到的边（注意我们的图里任何一条边都可以通到D）。

引理二：假设所有的 、 都是前文所述初始值。对于任何一条边 和一个顶点 ，如果 ，或者 ，或者“ 可以通到 且 与 不冲突“（三种说法等价），那么就一定存在一条从 到 的路径，路径上每条边与 、 都不冲突（换言之，此路径包含在 内 ）。

证明：如果 和 在同一“小节”之内，显然结论是成立的： 只能是该“小节”右端的端点或者是该“小节”的中点，前一种情况 可直接连到 （至多向前一步走，这一条边与 标注相同，故与 不冲突），后一种情况 就是 的右端。

现在假设二者不在一个“小节”之内。我们从 所在“小节“的右端出发（同上面 是小节右端的情形，至多向前一步走，且走的边与 标注相同），一小节一小节地向右前进，每小节有两条或者三条路径可选，下面说明总有一条是和 、 都不冲突的：

1. 倘若是两条路径，则说明是在“变量部分”，两条路径都不可能与 冲突（因为跟 标注的不是同一个变量），只要选择与 不冲突的那条边即可（两条路径是对同一变量的不同赋值，至多有一条与 冲突）。
2. 倘若是三条路径，那么即便其中一条与 冲突、一条与 冲突，还是有一条可选（注意反例之中每个子句都是3个不同的变量 ，这三条路径的标注是关于不同变量的，所以 、 分别只能和至多一条路径有冲突）。

如果 是端点，则这样就可以直接前进到 。如果 是中点，则走到 所在“小节“的左端点之后，在前行一步即可（走的这条边与 在冲突方面完全一致，因此不与 冲突）。

下面的引理说明operator3大多数情况下无效（除了operator4中第(1)步靠外面的Comp）。

引理三： 假设所有的 、 都是前文所述初始值。那么对所有顶点 ， 都和 完全一样（这里的Comp是第3页的operator3）。

证明：这里，operator3中的ES就是 。下面按照步骤一一验证。

来看第(2)步，对于任何一条 ，根据引理二， 之中包含一条 到 （即 到 ）的路径，因此 之中包含一条 到 的路径。所以这一步 之中任何一条边都不会被删去。（吐槽一下，这里的 纯粹就是冗余的，很显然对于任何一个集合K和任何一个图，“ 之中含有 到 的路径”当且仅当“K中含有这样的路径”。我认为这篇论文大多数操作都可以理清、写的更简洁、甚至去除，作者似乎并没有归纳整理的能力。）

既然第(2)步不变，那么第(3)步也不会变，在反例图中，从 出发可以通到任何一条边，当然也包含 中所有的边。

综上，把 经过Comp操作之后，它不会改变。

下面的引理在后文中会用到。

引理四：给三条边 ， 可以连通到 ， 可以连通到 ，且这三条边两两互不冲突，那么就一定存在一条从 到 、经过 全部三边的路径，其上每条边都与 不冲突（可能有的边与 冲突）。注意这里的“路径”就是图连通意义下的路径，不考虑 的限制。

证明： 的两端必为一个“端点”，一个“中点”，设中点为 。则任何一条边（特别地， ）与 冲突当且仅当它与 冲突。根据引理二，可以找到一条 到 的路径，路径上每条边与 都不冲突（故与 不冲突）。如果 是 的右端，则此路径已经包含 了。如果 是 的左端，则延长这条路径使它包含 。接下来，只要调整这条路径让它经过 即可。

如果 在三个不同的“小节”，那么我们只要路径上 所在小节的那部分改成经过 即可（调整该小节的2条或者0条边）。由于 两两不冲突，新路径上每条边仍然与 不冲突。而另一方面，如果 在同一“小节“，则路径必然已经经过 。同理，如果 在同一“小节”也不需要调整。

下面的引理说明operator4无效。

引理五：假设所有的 、 都是前文所述初始值。对任何一条边 ， （即 ）， 都不会改变 （这里的Change就是第4页的operator4）。

证明：请不要被第4页Change的定义吓到。那么长的一个式子，肉眼匹配括号都很有难度，一会用 一会用英文"contains"，但其实完全可以写的更简明。我真的怀疑这种写法是不是纯粹就是忽悠？

我们来看第(1)步。

首先根据引理三， 在我们的图里其实和 是一样的，替换掉。把式子中大括号“{}“所定义的集合记作K。这个大式子实际就是 ，而 K的定义如下：给定两条边 和 ，K包含所有的边 使得 包含有 和 。

注意这里三条边从左至右的顺序是 、 、 。我们下面分两种情况找到一个 （找一个即可，感兴趣的读者可以自行思考K的值。）

1. 如果 是一个“中点”，就取 前面的那条边为 。这条边的标注和 完全相同，故它和 都不冲突。
2. 如果 是一个“端点”，就取 前面一小节中和 都不冲突的、终点为 的一条边。这样的边一定存在：
   如果 前面一小节在“子句部分”，那么它有3条路径，其标注是关于3个不同变量的，至多有一个和 冲突，一个和 冲突，还有一个可选。
   如果 前面一小节在“变量部分”，那么它有两条路径，其上标注是关于同一个变量的不同赋值。由 知 与 不冲突，它们的标注不可能是同一变量的不同赋值。故两条路径中必有一条与 与 都不冲突。

两种情况下我们都找到了一条边 ，与 与 不冲突。接下来要证明它在K中。根据引理四，我们可以找到一条从 到 的路径，途经 ，且上面每条边都和 不冲突（因而与 不冲突）。用符号表达，此条由 到 的路径每条边都在 之中。K的定义满足，故 。

接下来，显然有 ，因为 可以连通到任何一条边。

最后，我们说明 。来看operator3 Comp的第(2)步，根据“假设1”（见“四、反例和假设”）， 不会在这一步被去掉。而第(3)步，即取 也不能将这条边去除，因为 可以连到这条边，且这条边与 相接。

这样，我就证明了operator4之中，第(1)步的集合永远非空， 会留在 中。

再来看operator4的第(2)步，这显然没有作用，因为 没有变化，仍然是可以从 出发可以连通到的、与 不冲突的边的集合，且每条边都可以通到 ，故取 没有作用。

综上，operator4对于任何一条边 都没有作用。根据“假设2”（见“四、反例和假设”），operator4不能用在 的边上，也就是说事实上operator4完全没有作用。

下面的引理说明第5页算法中2.3步第一行无效。

引理六：假设所有的 、 都是前文所述初始值。给定两条边 和 ，设 的右端点在 。则对于任何 ，都存在一个在 的点 ，以及一条由 到 、途经 的路径，其上每条边都与 、 不冲突（可能有的边和 冲突）。

证明：如果 ，考虑所有从 到 的边（记这些边组成的集合为 ），下面证明必有一条 与 都不冲突，并且从 可以连通到 。分情况讨论：

1. 如果 与 在同一个“小节”内，那么只要取 为 后面相邻的边即可（ 为同一小节的某一条路径，标注相同）。
   下面假设 与 在不同的小节，显然在这个假设之下， 一定是可以连通到 中任何一条边的，我们只要找到 与 都不冲突就可以了。
2. 如果 在“变量部分”，则 ，且这两条边上的标注是对同一个变量的不同赋值，必有一条边和 都不冲突（由 知 与 不冲突）。
3. 如果 在“子句部分”，则 ，且这三条边是关于不同变量的， 分别只可能和这三条边中的一条有冲突，还剩至少一条可以选作 。

找到之后，直接对 用引理四就得到了结论（与 不冲突可推出与 不冲突）。

下面再来考虑 的情况。此时只要取 为 的右端点即可。具体来说，根据引理二，我们可以找到一条从 到 的路径，其上每边都和 、 不冲突。我们只需考虑这条边不经过 的情况。此时， 一定不是中点（否则到 必经 ），且 和 不在一个小节中（否则由 出发必过 ）。我们只要调整最后一个小节的路径，改成经 到 。路径上每条边（新引进了 和它前面的有相同标注的边）仍然和 、 不冲突。

最后，我们来验证论文第5页的算法。

步骤1，就是计算 的初始值，已经由引理一给出。

步骤2.1，根据引理五，没有任何作用。

步骤2.2，根据引理三，没有任何作用。

步骤2.3的第一步，先由引理三知道 就是 。然后，取 ， 为 中的任何一边，应用引理六，我们可以在 中找到一个点 ，和一条 到 途经 的路径，其上每边都在 中，因此我们有 。这也就说明了 中的任何一条边 都出现在右边的并集中， 不会被改变。

步骤2.3的第二步，显然不会改变 ，因为 包含的都是 能连通到的边，且任何一条边都可以连通到 。

这样，整个算法完全不能改变 、 的值。算法的最后一步，在此应用引理三，由 知算法的输出是“符合条件的路径存在”，算法错误。

六、附录：关于P、NP等的背景知识

这些都是关于“复杂性”的一些概念。所谓复杂性，就是研究一个问题有多复杂，比如某某问题必须要多长时间才能解决（从数学上证明不可能在更短的时间内用计算机解决）。从某种意义上讲，“复杂性”和“算法”是相反的，“算法”是解决问题，“复杂性”是证明算法不存在。

有点神奇是不是？如果读者对数学比较敏感，立刻就会意识到两个重要的问题：

第一，怎么定义“计算机”？一般来说，我们用的是“图灵机”这种抽象模型，大致相当于普通的计算机加上无限的内存，并提前给定一个有限长的程序。

第二，什么是一个“问题”，什么是“解决”？具体是怎样的模型？这里的“问题”一般就是“是否”问题，输入一些内容，要求机器输出一个“是”或者“否”。比如上述的MSP，输入就是图以及所有的E(v)，输出就是问题所要求的路径是否存在。（只要输出“是”或“否”，这是为了简便。对于MSP问题，你如果有了一台输出“是否”的机器，那么你完全可以利用它造一台输出整条路径的机器，这个留作练习题。）

所谓P，就是多项式时间可以解决的问题的集合。具体的说，存在一个多项式f(n)，当输入大小是n时（对于MSP，输入大小就是图和所有E(v)所占的空间），机器在f(n)步之内给出答案。多项式时间可解决，在很多情况下就是说“问题比较容易”（当然不是所有情况都是如此）。

所谓NP，同样是多项式时间内可解决的问题的集合，但是机器的模型要改一改。先举个例子，写过程序的知道“随机数”这个概念，你可以把随机数看作一个单独的输入源，你的程序读n个随机的bit，实际上有2^n种不同的执行路径（想象一棵二叉树），一个随机的程序往往要在这2^n个路径中大多数都运行正确，这样的程序才有意义（可以多次运行提高正确性）。NP所要的机器，也有一个单独的输入源，但是要求放松了，当标准答案为“是”的时候，只要有一条路径运行正确、输出“是”即可。为方便理解，我给出几个常见的等价说法：

1. 存在一个0-1序列，当它作为输入源的时候，程序多项式时间内结束并输出“是”
2. 给机器加上一个“猜”的功能，每一步可以猜（类似于左拐还是右拐），且犹如神助永远猜对。
3. 存在一个证明答案为“是”的证明，程序虽不知道这个证明，但如果给了证明就可以在多项式时间内验证它。

（值得注意的是，这个定义并不对称。当问题答案为“否”的时候，并不是只要有一个输入源使程序输出“否“就可以，而是不能有一个任何输入源让程序输出“是”，即所有的输入源都得让程序输出“否”。）

MSP问题显然是在NP之内的。比如按照第2个定义，如果答案为“是”（即路径存在），那么机器可以先猜一条路径，然后验证它确实是从S到D、确实满足E(v)的限制。或者按照第1、3个定义，把这条路径当作输入源、或是证明，输入给程序，程序完全可以在多项式时间内检验。

打个比方，NP有点像“数学题”。给一道数学证明题，怎么证可能很难，每一步都有很多种方法可以尝试，没有经验的人要靠运气；但如果给了证明，就不难验证正确性，只要一步一步检验逻辑是否正确即可（机械劳动）。NP就是这种难度。有些更难的问题，多项式时间验证都做不到。

最后一个概念，NP-Complete就是NP之中最难的问题。MSP就属于NP-Complete。具体来说，NP中的任何一个问题，都能用多项式时间（传统机器，不带“猜”的功能）把它的输入“转变”到一个MSP问题的输入（图+E(v)），并且原问题答案为“是”等价于MSP问题的答案为“是”。这样一来，只要找到一个解决MSP问题的多项式时间算法，那么所有NP之中的问题都可以转化为MSP后再解决，也就是说P=NP。

常见的NP-Complete问题有很多，比如3SAT，Hamiltonian circuit等等，还有作者提出的MSP，这些问题都可以互相转化，只要解决了一个，NP就全部解决。证明一个问题是NP-Complete，其实往往并不高深，只要找一个已知的NP-Complete的问题规约到这个问题即可。

最后，我再介绍一下文中用到的3SAT问题。这个问题很简单，就是给一堆Boolean value ，然后一大堆至多三个变量的“逻辑或”表达式（叫做“子句“），比如 （三者至少有一个是1）、 （ 、 取反、 之中至少有一个是1）、 （三者之中至少有一个0）。给定这些之后，请问是否存在一组 的赋值使得所有的clause都成立？这个问题显然在NP之中。机器只要猜一下每一个 的值，再验证所有表达式都成立，即可。