文档章节

计算复杂性读书笔记(二): 论怎么把一个证明写得有意思

Airship
 Airship
发布于 2015/02/08 23:07
字数 6169
阅读 243
收藏 5

计算复杂性读书笔记(二): 论怎么把一个证明写得有意思

 比特猪

quanzz1129@gmail.com

 

首先是版权声明,版权归属为:东南大学知识科学与工程实验室(kselab@seu )。其实这个系列笔记实在是因为自己太笨,没法了解很多东西,觉得有必要写下来梳理一下。所以不管大家看着有帮助也好,嗤之以鼻也好,实在是没有必要转载。虽然文拙笔劣,不过毕竟也是大冬天花时间一个个字敲下来的,所以如果非要转载,我也希望注明出处。如能致此,感戴莫名!

 

2.1. 补充

 

        文蛤时期,伟大的先辈发明出了一种优雅活泼奔放的喷人方法:文字皮逗。大家伙儿看谁比自己牛逼,就买横幅写大字,然后各种喷。 这个工具沿用到今天就演变成了论坛里时常聚众发生的口水战,看到别人在装,就会实在看不下去。“装”是该骂,我也看不下去!所以我要说的是,我的系列笔记绝对没有“装”的嫌疑!

        上一篇笔记中,我们不断地将关注的范围缩小,最后我们集中在这样一些“计算问题”上:

 

①首先这个问题得有解。关于“猪睡觉会不会做梦”这个问题,好像在瑞典哪个大学有个研究小组已经取得了一些进展,而且准备冲击逗比诺贝尔奖。所以这个问题可能有解。对于一个有解的问题,问题本身和解构成了二元关系,所以我们可以用一个二元关系来描述一个问题:R= {<x1, y1>, <x2, y2>,…,<xn, yn>},每一个二元对的左部是这个问题的输入,右部是这个输入对应的输出。

②这个问题是一个多项式平衡(polynomialbounded)的问题。即是说,问题的输出规模是输入规模的多项式级别。关于什么是“规模”?既然主要是计算机领域在考察P=NP这个问题,我们就假设是用计算机去解决计算问题,而计算机最后都会将问题编码成二进制形式。所以,我们约定一下,这里的规模指的就是编码后,输入和输出的二进制串的长度。但是,这个约定可能让搞量子计算机,光子计算机,还有其它什么子计算机的人不爽了。这个,只能拜托这些人迁就一下了,我们这里很俗,只能用用电子计算机。

③这个问题应该对任意输入都“鲁棒”。注意,这里的“鲁”没有加提手旁,所以它是一个形容词,不是动词。特别地,对于判定问题,它的特征函数应该是全函数。通俗一点来讲,给一个任意的输入,这个问题都能进行处理。这里其实有点模棱两可,我们在谈论一个判定问题的时候,其实应该允许它的特征函数不是全函数:比如“x是不是质数?”这个判定问题。如果我们将考察的域扩大到实数范围,很显然,特征函数Prime(x)在无理数上是没有定义的,所以你得事先判断x是不是一个合法的输入,以达到“鲁棒”性。实际上,“鲁棒”是因为我们将特征函数Prime(x)和另一个函数xN N是大于0的自然数)进行了复合,然后得到了一个新的特征函数,这个特征函数是一个条件式,如下:

 

 

这个新的特征函数f(x)是一个实数域上的全函数——在实数这个域上都有定义。所以确切滴说,我们并不是只关注特征函数是全函数的判定问题,我们关注的判定问题是都可以改造成一个特征函数为全函数的问题。所以,约定后面所遇到的问题(包括搜索问题)对于任何输入都是有定义的。

 

将关注范围限定好以后,我们又在上面定义了四个问题类:PFPCPNP。下面,我们试图通过简单的叙述性语言来描述这四个类(这个做法其实很危险,因为说不好就错了),首先声明,下面所谈到的所有多项式,都是针对输入规模的多项式

 

 PFpolynomialfinding),给定一个输入,多项式时间内可以找到一个解的搜索问题。这里找到一个解就可以。要明确的是,不是找最优解,比如:“怎么提高大学的研究水平?”这个问题,它有很多解。当然,在这个体制里的人可以慷慨地说上一堆,但确实是存在一个最优解,小生不才,不小心发现了这个解,没错儿!“让学生被《劳动法》保护起来!”一般地,找最优解可能相当复杂,这里是找到一个解就可以,很多情况下,你也够用了。比如,刚才这个问题,有一个解是“将博士生的补贴从每月1300元提高到1500元”,我大概了解了一下,似乎国内很多理工类大学都认为这个解已经完全够用了。不扯淡了,继续。

 

 PCpolynomialcheckable),首先这是一个搜索问题,给定一个输入,你不一定能在多项式时间内找到一个解,但是如果给你一个解答,你可以在多项式时间内验证这个解答是不是这个输入的正确解答。有点绕,但是soeasy的,就不展开讨论了。

 

 Ppolynomial),针对判定问题,给定一个输入,能在多项式时间内找到答案(是(true)或否(false))。实际上,对于判定问题,其定义域可以分为两类,类1对应的输出为“是”,类2对应的输出为“否”。所以P问题也可以看成“能在多项式时间内判定一个输入在前述哪类集合里”的判定问题。进一步地,这也是1.4讲的为什么一个判定问题可以仅仅用一个集合来描述,因为单用类1或者类2可以等价地把这个判定问题描述清楚了,而一般地,我们都用类1来描述判定问题。

 

 NPnondeterministicpolynomial),它针对判定问题而言,给一个输入,我不一定能在多项式时间内找到答案是“是”还是“否”,但是你给我一个线索,我就可以在多项式时间内判断出来。这个比较难理解,笔记1里说NP问题是“判断某个PC问题是否有解”的判定问题。其实这样说还是不容易理解。我们重新贴上NP的定义:

 

定义6NPnondeterministic polynomial一个判定问题SNP问题,当且仅当,存在一个PC类问题R,使得S = dom(R)

 

这个定义比通过线索来定义还要精辟。

所以,这里的关键是,那个“线索”是啥?回到PC问题,对于一个PC问题,给一个解答,可以在多项式时间内验证这个解答是不是对应输入的解答。没错儿,对于PC问题,这个事先给的解答就是“线索”。如果我们把NP问题对应到一个PC问题,那么我们就可以给些线索来多项式时间内解决问题了。

说的什么玩意儿啊,上栗子!

 

       问题4:判断x是不是质数?

 

   这是一个判定问题。判断质数其实是多项式时间内可以解决的(人们研究了好长时间,02年被三个阿三证明出可以在多项式时间内判定质数 [1]),所以问题4其实是P问题。那它是不是一个NP问题呢。我们要找线索,那么我们先找一个PC问题,定义6里说“存在一个PC问题”,所以我们找到一个就行。我找到下面这个PC问题:

 

    问题5 x的不是1和它本身的因子?

 

问题5是一个搜索问题,它也是PC类问题,任意给一个数,可以在多项式时间内判断是不是它的“不是1和它本身”的因子。我们先把这个问题形式化,就是找一个二元关系R4,因为01是特殊情况,为了方便叙述,我们把它们排除在考察的域之外,所以R4={<4,2>,<6,2>,<6,3>,…},但是质数本身也是合法输入,只是它们对应的输出为空。给定一个输入,我们给一个线索:一个x的不是1和它本身的因子y,我们可以在多项式时间内判断<x,y>在不在R4中。回到问题4,我们把那个因子作为线索,那当然可以在多项式时间内解决问题4。所以问题4肯定也是一个NP问题。这里的线索,学名叫证书或者证据(proof),很多定义都是基于给定的一个证书。

 

给了这四类问题之后,我们又接着证明了PNP。有了上面的理解,PNP的证明过程直观上来讲:对于P问题,本身已经可以在多项式时间内解决了,所以你给任何线索都无关紧要,所以它当然也是NP问题。

反过来,“NP是不是包含于P”这个问题,问的其实是“是不是存在一些集合,我不能很快(多项式时间内)判断某个元素是不是在这个集合,但是如果你给我一个线索,我可以很快(多项式时间内)作出判断”,这件事儿不好办,要是你看了我的笔记证明出来了,别忘了挂我的名字。(我是认真的!)

 

 

2.2. 选择

 

        看到2.1,如果你仅仅是想了解一下什么是P=?NP问题,那么你可以不用再继续看下去了。下面就是好事者怎么去玩儿的领域了,你要是继续往下看就说明你真的感兴趣,并且有成为好事者的资质!那么是继续还是结束,现在由你选择。

 

2.3. 继续

 

       嗯,我们继续吧。其实多了解一点东西没有坏处,当然我是那种懒得去学新东西的人。不过,能掌握很多东西,对一个人装B是大有好处的,这个大家可以瞄一眼知乎就能深刻地认识这个道理了。拿我举例子吧,我经常用我的Mac上装的Win7开发Android啥的(突然感觉自己在三个公司之间游刃有余),嗯,就这点伎俩,所以不必仰视我。

      

2.4. 等价

 

       之前我们说,人们看待一个“计算问题”更符合情理的是将它看成一个“搜索问题”——即,搜索问题的解。也由之,红书定义了两个计算复杂类:PFPC类问题。然后在之上给出了PNP问题。接着,我们证明了PNPP=?NP这个问题也变成了NP⊆?P这个问题。如果回到我们直观上的搜索问题,NP⊆?P是不是在问PC?PF呢?也就是说,给一个线索,我可以很快(多项式时间内)验证是不是输入的解,那么我是不是也能很快求得这个输入的一个解呢?

        下面的证明就要说明NP⊆?PPC?PF是等价的。一旦证明了这两者是等价的,我们就可以仅仅将注意力放在判定问题上了,也就是,我们只用去关注PNP问题了。当然下面的证明,你若是不想看,可以直接跳到2.5节,你要是感兴趣可以䁖一眼。

 

定理2 NPP 当前仅当 PCPF

 

证明,

先证:PCPF  NP P假设有这么一个NP问题S,那么按照NP问题的定义,存在一个PC问题R,并且S=dom(R)。因为按照前提假设“PCPF”,对于任意的输入xdom(R),存在一个算法A,能在多项式时间内找出x的一个解,或者如果x没有解,A(x)=。在A的基础上,我们构造一个算法A’,令:

 

 

利用A’,我们可以在多项式时间内判断x在不在S中,因而SP,进一步地有NPP

        下面证明: NP P  PCPF设有这么一个PC问题RPC问题说的是,给一个输入输出对(x,y),我可以在多项式时间内判断(x,y)是否在R中(或者,多项式时间内判断y是不是x的一个解)。根据R,我们构造一个NP问题S,由定义6,这个NP问题可以是S=dom(R)。而由假设条件“NP P”,我们有,存在一个算法A,给定任意一个输入x,可以在多项式时间内判断x是否在S中。那么问题来了,我们能够否在A的基础上构造一个算法A’,使得可以在多项式时间内找到x的一个解。

按照定义6,这个事儿不好办。实际上定义6反过来也说得是“一个搜索问题RPC问题,当且仅当,存在一个NP类问题S,使得给一个输入xS和一个线索y,可以在多项式时间内判断(x,y)R”所以,我们可以任意构造一个对应的NP问题,我们不采用定义6的构造方式,我们构造一个新的NP问题:S’={xy’|xdom(R)⋀∃y”,s.t.(x, y’y”)R},意思说的是,我们将R的一个任意输入x,和它对应的一个解y的任意前缀组成的串(这里假设已经编码成了01串)作为S’的元素。由于这些问题都是多项式平衡的,这里S’的规模肯定是S的多项式级别,即:|S’|<=p(|S|)。由假设条件“NP P”,我们有,存在一个算法A,给定任意一个输入x,可以在多项式时间内判断x是否在S’中。现在,我们可以根据算法A构造这么这个算法A’来找到x的一个解:

 

 

while循环其实是遍历所有可能的01串,看看哪一个是x的解。但是由于假设条件“NP P”,也就是任意的串xy’可以多项式时间内判断在不在S’内,如果y’后面添一个0也在S’内,那么让y’0代替y’;如果y’后面添一个1S’内,那么让y’1代替y’。这个过程是多项式的(因为多项式平衡),因而A’算法也是多项式时间内可以停机的。因此,RPF,也就有了PCPF。证毕。

 

 

2.5. 同构

 

        我相信一定不会有很多人喜欢看像2.4中这样的证明过程,不是因为大家觉得自己没有数学方面的兴趣,而是更多的人会想,有这个闲情还不如想想买什么股,研究研究K线图啥的!真正看这些证明会产生多巴胺的,在我们“普通人”看来就已经是奇葩了。

        所以,我有时会想,要是哪天,数学类教材上把这些证明写得很有意思,那该多好,至少我们这些凡人会觉得数学家还是体恤民心的嘛。这里的有意思不是让数学家感到快感的那种“有意思”,而真的是“有意思”的那种有意思。也许你会说,很多教材都做到了啊,把一个深奥晦涩的证明用普通人看得懂的方式讲明白了啊。其实这些教材做的是这样的事:首先你已经知道我们要证明什么了吧,比如2.4中要证明NP⊆?PPC?PF是等价的,OK,那这个普通人看得懂的方式其实是在说“你就甭管细节了,你也看不懂,不管怎样我是帮你证明出来了,你看你已经懂了结论,不是挺好的嘛。”

        不过毕竟,有些好事者并不接受上述这种“普通人看得懂的方式”,他们想了解到底这个结论是怎么来的。任何通过作者理解归纳过后的叙述都会让他们不满足,因为毕竟不是自己理解得出来的。这样一来,又要陷入得把详细证明列出来而让其他人不爽的尴尬境地。要解决这个问题,只有一个方法:同构

       就像爱因斯坦给小伙子解释相对论,我们也找一个所要证明的问题(比如NP⊆?PPC?PF是等价的)的同构的问题,这个同构的问题要“够俗,够萌,够贱”。然后证明这个“三够”问题。这样既给出了详细过程,又使得“普通人都看得懂”,岂不是一举两得!

       同构是一个伟大的思想,这个思想属于自然界,是不以人的意志为转移的。W老师课上推荐了一本书:《GEB》,中文名《集异壁之大成》。书的作者是搞逻辑的,某天发现哥德尔的数理逻辑、艾舍尔的绘画还有巴赫的音乐竟然是那样地相像,这个“像”就是他们在很多方面竟然都是同构的。于是,作者脑洞大开,洋洋洒洒挥墨千页,分娩出了这部神一般存在的书。

      大家感兴趣可以把这本书找过来拜一拜。那么接下来,我也试着去找定理2的同构问题。思来想去,找到了一个“特俗,特贱,特没节操”的“三特”问题。既然定理2涉及到了四个对象:PCPFNP以及P。那么我们首先把这四个对象同构到这个三特问题的四个对象上。先声明,因为目前天朝社会基本上是一个看脸的社会,所以为了让大部分人看得懂,找到了下面这个三特问题,另外,请大家不要对号入座!

 

        PF对应到这个问题:长得漂亮的人会发生什么?一般而言,长得漂亮的人会发生什么事情都比较“简单易懂”,所以可以在“很短的时间段内”找到一个解,比如“长得漂亮的人比较受校长的青睐”等等之类的。

        PC 对应到这个问题: 形象好的人会发生什么?形象好的人,我们从内心里尊敬他们,但是一定要说他们因为形象好会发什么,我们不一定很快找到一个答案。但是你给我一个线索,比如“食堂打饭时大妈特别热情地多盛了一块肉”,那我可以判断一定是因为这家伙已经坚持刷牙一个礼拜了。然后暗暗地痛下决心,从明天开始也坚持刷牙!

        P对应到这个问题:长得漂亮的人。我们知道判定问题可以用一个集合来描述,这里也用一类特定的集合来描述。这个问题详细点就是在问“x长得漂不漂亮?”

      NP对应到这个问题:形象好的人。同样,这个问题有一个对应的PC问题,给一个线索,我可以验证某个人是不是形象好的人。

 

     现在我们已经证明了PNP,对应到上面就是“漂亮的人形象都很好”。也许具有人文关怀的你要喷我了,说我“三特”,但请相信我,很多人觉得漂亮的人形象好并不是根据他们的穿着打扮是否得体,而是根据自己肾上腺素的分泌量。

     进一步地,定理2翻译过来就是“一件因为你形象好而发生的事情一定也是因为你漂亮”和“形象好就是漂亮”是等价的。说一件发生在我身上的事情。我们家楼下住着一个女神。大四的时候,因为要经常出去面试笔试,所以回到家也习惯穿着西装(因为经常一段时间,我都懒得换衣服)。每天出去前,都是西装革履,梳妆打扮一番。某天在电梯里遇见女神,自己已经不能呼吸了,然后她的东西掉落的一刹那,我以迅雷不及掩耳盗铃之势接住后还给了她,她愣了一下,向我莞尔一笑,说了声“谢谢。”那个时候,我无比相信,这就是缘分,这是上天安排的,没办法,一定是因为漂亮的人之间是相互吸引的。于是接下来几天都甜蜜地失眠了。后来几次,在电梯里碰见她,她都向我点头致意,我想,恩,这份安排已经再明显不过了。可是,万万没想到!!有一天早上,我没有刷牙,没有梳头,还穿着睡衣下楼去拿牛奶,意想不到地在电梯里遇见了她,而且也意想不到地,她就像不认识我一样,对我熟视无睹,我的心在那一刻,碎了。这之后,我成熟了,长大了,然后,就没有然后了。相信我,NP肯定是不包含于P的!

 

      大家不用为我难过,我只想让你们知道:“同构”是一个伟大的思想。而这个伟大的思想在接下来会引导我们发现另一件神奇的东西:归约。

 

 

2.6. 插话

 

      红书中给了一段用哲学的观点来看P=?NP这个问题的叙述。这里我只是搬运而已。

      说哲学家以前都坚信:如果一个系统还有在这之上的问题可以被很好地形式化地描述,那么这些问题一定可以解出来。这个想法一直到20世纪还被大家相信着,以至于希尔伯特一帮人准备搞出一个宇宙大一统的数学系统。然后,突然有一天,哥德尔把这个梦打破了。我就不介绍哥德尔不完备定理对当时的世界带来多大的风暴,要介绍的话也是贴的百度百科。举个简单的例子:

 

下面这句话是错的,

上面这句话是错的。

 

   究竟这两句话谁对谁错,大家绕一绕吧。拿普通人的理解,哥德尔不完备定理其实指出了,系统中的某个错误或者不一致不一定是通过系统本身导致的(或者被系统定义出来的),而是由于更复杂、或者更无法理解的原因导致。

      回到P=?NP的问题,通常人们会直观地认为,一个问题可以多项式时间验证其解答,不一定就能多项式时间求得它的解。如果把哥德尔不完备定理作为佐证,那么似乎也会存在某个NP问题,它求取解的过程可能由更复杂、或者更无法理解的因素作用着,而这些因素也使得这个过程不能在多项式时间内高效地完成。


2.7.  参考文献

 

[1] M. Agrawal, N. Kayal, and N.Saxena, “PRIMES is in P”, Ann. of Math. (2) 160:2 (2004), 781–793.

本文转载自:http://user.qzone.qq.com/757296636/blog/1420644255

Airship
粉丝 46
博文 1084
码字总数 21664
作品 0
南京
高级程序员
私信 提问
计算复杂性读书笔记(三): 同构,自指,停机问题

很久以前,举国兴盛各种仙术邪道,每个派别的高德大师会给弟子们传授独门心法,通俗地来讲就是“怎么快速地获得幸福”,每次传授完了之后,他们会例行地来一句:“千万别跟别人说是我说的,不...

Airship
2015/02/15
316
0
0133| 讲几个我读书的小习惯

开始写作以后,对输入的倒逼作用越来越明显。最大的一个就是自己的读书效率和读书吸收度比以前高了不少。今天正好总结一下自己在读书过程中的几个习惯,同时也促使自己改进优化。 习惯一:读...

吴海燕_YuBin
01/22
0
0
我的 2017 年度盘点

一、Core Topics Learning based on full English. Operating System Kernel & Dynamic tracking & Go Programming Language. Lincoln Foundation & Absolutism Research. 二、年度成果 2.1 ......

RiboseYim
2017/12/30
0
0
告诉你1年读100本书的方法

《书都不会读,你还想成功》是一本小说,由韩国作家二志成和郑会一合著,书的内容为一个焦躁的职场人士通过读书的方式,彻底改变了自己的思维方式,进而改变了自己的生活的故事。 下面就说说...

anda0109
2016/12/22
0
0
国富论--读书笔记

读一本书如果读了就忘,不做笔记,用一个比较粗俗的话来形容的就是,有屁用 但如果连20几天都坚持不下去,那你就等着人工智能来抢你的工作-----搬砖。 劳动生产力的改良原因,究竟在哪里,劳...

眉间雪
2017/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周二乱弹 —— 他只能用这个办法劝你注意身体了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @-冰冰棒- :#今日歌曲推荐# Kodaline《High Hopes》 《High Hopes》- Kodaline 手机党少年们想听歌,请使劲儿戳(这里) @xiaoshiyue :仙女...

小小编辑
22分钟前
649
14
Spring Boot Actuator 整合 Prometheus

简介 Spring Boot 自带监控功能 Actuator,可以帮助实现对程序内部运行情况监控,比如监控状况、Bean加载情况、环境变量、日志信息、线程信息等。这一节结合 Prometheus 、Grafana 来更加直观...

程序员果果
31分钟前
8
0
Linux文件查找命令详解

对于文件查找,我们最好用的还是属于find命令了,在说find命令之前,先把另外几个查找命令介绍一下。 目录 0x01 查询命令介绍 0x02 find命令介绍 0x01 查询命令介绍 在介绍之前,首先先了解一...

无心的梦呓
31分钟前
5
0
快速掌握的测试用例优先级划分方法

怎么样的设计才能算测试用例 引自:IEEE Standard 610 (1990): A set of test inputs, execution conditions, and expected results developed for a particular objective, such as to exe......

测者陈磊
35分钟前
4
0
[mycat]Attribute value "roadNodeId,version" of type NMTOKEN must be a name token

不能逗号配两个字段的主键 primaryKey="roadNodeId,version" Caused by: io.mycat.config.util.ConfigException: org.xml.sax.SAXParseException; lineNumber: 7; columnNumber: 105; Attrib......

Danni3
40分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部