登陆注册
14463000000062

第62章 NP=P?

2000年初,美国克雷数学研究所的科学顾问委员会选定了七个‘千年大奖问题’,也就是所谓的‘世界七大数学难题’。

克雷数学研究所的董事会还建立了七百万美元的大奖基金,若能解开任何一个‘千年大奖问题’,都可以获得当中的一百万美元奖励。

这七个问题分别是‘NP完全问题’、‘霍奇猜想’、‘庞加莱猜想’、‘黎曼假设’、‘杨-米尔斯存在性和质量缺口’、‘纳卫尔-斯托可方程的存在性与光滑性’以及‘BSD猜想’,七个问题中,现在就只有‘庞加莱猜想’已经被破解,还余下其他六个。

但凡研究数学的人,都不得不去接触并尝试挑战这些问题,因为这些问题都是关于数学基本理论的,而且这些问题的解决将对数学理论的发展和应用的深化有巨大推动的产生。

这里我们只谈当中的‘NP完全问题’,NP是Non-deterministic-Polynomiald的缩写,也即‘多项式复杂程度的非确定性问题’之意。简单的写法是‘NP=P?’,问题就在这个问号上,到底是NP等于P,还是NP不等于P?也就是说任何一个能通过一个多项式时间算法转换为某个NP问题的NP问题,我们就说这个NP问题为‘NP完全问题’。

举个最简单的例子,在一个周六的晚上,你去参加一个大型晚会,由于你太过紧张的缘故,你试图想要知道这大厅中是否有你认识的人,好减少这股因紧张而形成的局促不安感。

一般情况下,你必得环顾整个大厅,一个个地审视每一个人,才最终知晓看是否有你认识的人,但这种方法费时又费力,而若此时宴会的主人给予你暗示,说你或许认识那位正在甜点盘附近角落的罗丝女士。

因这个暗示,你不费一秒钟就扫视了那个地方,结果你发现宴会主人是正确的,那位罗丝女士正是你认识的人。

‘NP完全问题’本质上就是这样一个意思,生成问题的一个解通常比验证一个给定的解时要花费更多的时间。

也就是说如果有人告诉你,数13717421可以写成两个较小的数的乘积,你可能不知是否信他,因为这意味着你必得两个两个数地去验证,但他若不是那样告诉你,而是这样告诉你,数13717421可以分解为3607乘上3803,那么你就可以用一个袖珍计算器一下子就验证出这是否是对的。

由此可见,所谓的‘完全多项式非确定性问题’,其实都可以转换为一类叫做‘满足性问题的逻辑运算问题’,就像宴会中你可能要观察多人才能判断这些人中是否有你认识的人,可以变成验证宴会主人暗示的问题,以及数13717421可以写成两个较小的数的乘积这样可能会有多数答案的问题,可以变成直接验证3607乘上3803是否等于13717421的问题。

既然‘NP完全问题’的所有可能答案都可以在多项式时间内计算,人们于是就猜想,是否这类问题,存在一个确定性算法,可以将‘完全多项式非确定性问题’转换成‘满足性问题的逻辑运算问题’,如此一来,便能通过这个算法,在多项式时间内,直接算出或是搜寻出正确的答案呢?这就是著名的‘NP=P?’的猜想。

事实上,在学校时,知道答案与计算方法的老师,都会最大限度提示学生们关于问题如何计算,这种暗示,其实就是‘NP完全问题’。

若能将老师这种知道答案的结果,以某种确定性算法得出的话,学生们也就不需要老师的提醒,也能通过这样的算法来自己推断出问题的解法与答案,‘NP=P?’其实就是这样的一种理想化猜想。

之所以说是理想化,因为猜想‘NP=P?’的数学家,都在幻想是否存在着这样一种万能的解法,可以解决任何属于此类的问题。

其实这个问题的解答并不复杂,因为就算没有这样的万能算法,人们都可以从NP完全问题中解答出答案,就像那宴会以及数13717421,只不过需要你花大量的时间去一个一个验证罢了,但答案始终会在其中。

“‘NP=P?’就是试图简化这个发现过程。”

皐水奈深吸一口气,口中轻声说:“比如找大质数的问题,因为没有可推导的公式,你只能一步一步去推算下一个质数应该是什么。但像加减乘除之类,就明确多了,因为你只需要根据加减乘除的公式推导,就可以得到结果。所以说若能让找大质数的问题变成加减乘除般一目了然,就能节省很多的人力物力。”

“但正因为缺乏这样的万能公式发现,往往对于此类问题,人们要不像个傻。逼。一样一个一个去计算,但这是不切实际,因为这样的计算复杂程度是指数关系,会随着计算的时间、问题的复杂程度呈指数增长,很快就变得不可计算了。抑或为了节省时间,用碰运气的方式去随即挑答案代入验证。”

陆十郎听得皱起了眉头,皐水奈说的问题,其实他也深有体会,在小时候,家长之所以会不断提醒小孩子注意的事项,因为若让小孩子自己去理解的话,他只能一个一个去验证,有时会在犯下沉重的代价后才得到答案,青少年吸。毒严格上就是这个问题。

像高三升大学报专业时,如果此时有在社会上经历过的人提示的话,你就能选个日后在社会上含金量很高的专业去读,诸如法律、医生、金融等,一般这种时候最好不要询问老师意见,大多数老师都是从师范学校毕业后就直接过来教书的,严重缺乏这类的认知。

“呐,十郎,你知道基督教所谓的‘圣杯’吧?严格上,这所谓万能许愿杯,即这个能实现任何向其许愿之人愿望的过程,其实就是‘NP=P?’的问题。圣杯包含这样的万能算法,比如你许愿想要变成有钱人,根据‘NP=P?’的问题,会从无数让你变成有钱人的方法中挑出一种,诸如让你捡到一千万这样的方式来实现你的愿望。”

此时,皐水奈说道:“据说在某个地方,为了让所谓的圣杯显现,进行着以七人与召唤出来的使魔的形式来相互厮杀,到最后存活一人得到圣杯许愿资格的仪式。因为人本身是包含复杂多项性的生物,以此诞生的便是无穷无尽的欲望,以这样的七人集合在一起厮杀到最后一个存活,本身就是将这些多项性扼杀至唯一性的做法,以此来显现的圣杯,自然也就包含了这样的万能算法。”

圣杯等于‘NP=P?’,听着的陆十郎满脸意外的表情,对这所谓的七人圣杯战争产生了某种想象。

马上,他问道:“也就是说,你说的疯狗那什么‘NP函数之魔眼’,就是这样‘NP=P?’性质的魔眼?”

“嗯,不过,十郎,你只说对了一半。”

皐水奈故作高深的表情:“严格上,就算魔术也不可能做到完全的‘NP=P?’,也只能是偏向于自身某种爱好的‘NP=P?’。我会跟你说圣杯的事情,乃是完全的‘NP=P?’,等同于拥有圣杯一样的万能算法能力,按你们魔术世界的说法就是,‘NP=P?’其实也是根源大道的别称。魔术师最多只能做到无限接近,但要达到完全的‘NP=P?’,那已经不是魔术的范畴,而是真正的魔法!”

皐水奈的意思很简单,疯狗的魔眼并不是完全的‘NP=P?’,而是在他设定的范围内而得出的适合这个范围的‘NP=P?’算法,距离适应于世界万物的万能算法,还差得远,所以疯狗的魔眼称呼上才加上‘函数’之称,而不是‘NP完全之魔眼’。

在数学上,所谓的‘函数’是指一个量随着另一个量的变化而变化,或者说一个量中包含另一个量,表达式为y=f(x)。

一般的,在一个变化过程中,有两个变量x、y,如果给定一个x值,相应的就确定唯一的一个y,那么就称y是x的函数,其中x是自变量,y是因变量,x的取值范围叫做这个函数的定义域,相应y的取值范围叫做函数的值域。

定义域,值域以及对应法被称为函数的三要素,对解开函数至关重要。

疯狗的魔眼‘NP函数之魔眼’,在设定范围上定义在函数方面,换言之将原本的万能解法‘NP=P?’局限在了这样的片面算法上。

函数的值域相当于结果,要解开这个结果,必得知道定义域的范围以及两个变量之间的对应法。

向陆十郎发动魔眼攻击时,疯狗不是让其魔眼攻击的结果类似于‘兽杀之魔眼’吗?根据函数表达式为y=f(x),当时疯狗是让魔眼攻击的结果y与‘兽杀之魔眼’一样,然后设定某种不明的X,即定义域,再将比声音传播更快的攻击设定在f上,所以相乘的结果自然就得出类似于‘兽杀之魔眼’的攻击,但这攻击速度却比声音传播更快!

那么,要对付疯狗的魔眼,自然要在他的函数公式上下功夫。

皐水奈说,不管疯狗设定怎样的值域,这个值域必定与对应法y以及定义域x有某种关联,只要进行反推导的话,就能化被动为主动!

同类推荐
  • 斗神战纪

    斗神战纪

    这里是属于斗气使用者的世界,由职业斗士们组成的斗神联盟联合了努比斯大陆上面的七个大国,职业斗士已经融入了这个世界的政治、经济、军事、生活等的各个方面。箭头是一个生活在斗神联盟成员国天酬联邦的首都比尔市的贫民窟里头的孤儿。为了在这个弱肉强食的世界里生存下去,箭头和小伙伴们,不得不在斗士的道路上一直不断地变强、变强、再变强!感谢阅文书评团提供书评支持
  • 七剑至尊

    七剑至尊

    在那天道逝去的时代……在那纷争满天下的时代……他,经脉被曾经的天道所封印,他,年纪尚小却要入那江湖经历风与雨,他,即便手中之剑断去也未曾言弃!看,他手中一剑,化为七剑,笑傲天地寰宇,苍穹唯我独尊!
  • 极品邪尊

    极品邪尊

    给我一柄剑,我能刺破苍茫大地。给我一把刀,我能斩断无尽苍穹。神话,不论在哪里,都将辉煌!秦扬,曾经让整个地球都颤抖的男人,穿越到以武为尊的龙腾大陆,他将掀起无尽狂风。踩小人,披荆斩棘。拥美人,香玉满怀!“我一定要亲手宰了那个女人!”雪山之巅,他放声咆哮!
  • 异族:争霸

    异族:争霸

    不同的人生,不同的种族,在杀戮中前行,巅峰之上谁与争锋
  • 武战星河

    武战星河

    武圣秦毅转世重生,来到了以武为尊的天峰大陆。八方云动挥剑斩破,诸天幻灭唯我独尊。拳震八荒,剑扫六合,伏尸百万,成就无上武神。
热门推荐
  • 药师琉璃光七佛本愿功德经

    药师琉璃光七佛本愿功德经

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。汇聚授权电子版权。
  • 中国知识产权司法保护 2008

    中国知识产权司法保护 2008

    综述中国知识产权司法保护的概况与要点;解读最高人民法院关于知识产权的司法解释;研讨中国知识产权司法保护的时间问题。面对知识产权案件持续较快增长的艰巨任务,各级法院全面加强各项知识产权审判工作,审判职能不断强化,审判领域不断拓展,审判质量和效率不断提高,审判理论不断丰富,较好完成了知识产权审判任务,依法履行了知识产权审判职责,有效增强了知识产权司法权威,为建设创新型国家和构建和谐社会提供了及时有效的司法保障。
  • 红楼多娇

    红楼多娇

    为官的,家业凋零;富贵的,金银散尽;有恩的,死里逃生;无情的,分明报应。她们一家三口不做官不显富,倒是做了不少好事,所以命运之神才会特别眷顾。一场车祸,一个别样世界。酣梦醒来,老爸成了邢忠,老妈成了邢太太,女主呢?悲催的成了那个靠当衣服度日的邢岫烟。别人穿越,要么做林妹妹,要么做宝姐姐,最差也是个晴雯袭人之流吧,怎么到了她这儿,却是炮灰中的炮灰?好吧,既来之则安之,况且有亲爹有亲娘,半路上还捡了个身份不明的小包子,一家四口齐努力,不信炮灰没春天!简而言之,本文乃是......红楼炮灰一家携带包子强势逆袭!**********小荷的第二本红楼文,希望有所突破,希望大家继续支持小荷。没有看过《红楼夜话》的可以戳一下我,吼吼,另有将要完成作品《御朱门》等待大家爱抚
  • 逆圣独尊

    逆圣独尊

    意外陨落的散修,立志寻找前世爱人。执念支撑,尝遍千辛万苦;伊人相伴,凌驾四海八荒。且伴我,傲视寰宇,睥睨琼霄!
  • 阮籍集

    阮籍集

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。
  • 云叟住禅师语录

    云叟住禅师语录

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。汇聚授权电子版权。
  • 帝王娇宠

    帝王娇宠

    “陛下,今日倾君小姐在国子监打了张相家的公子。”“哦”龙椅上的人抬起头漫不经心问道,“倾儿可有受伤?”太监无语的翻翻白眼,陛下你就不问问什么事吗?你这样宠着倾君小姐真的好吗·····“陛下,今日林贵妃与倾君小姐在御花园发生口角倾君小姐一怒之下把贵妃推进了荷花池里。”“哦。”······陛下你能给点其他反应吗?“陛下,倾君小姐今日去了烟雨楼。”“嗯,派影卫好好跟着”龙椅上的人头也不抬的答道。“陛下,倾君小姐是跟逸王爷一起去的”太监犹豫的说道。啪···“你怎么不早说!”说完一阵风飘过····太监抬起头桌上只留下批阅了一半的奏折跟毛笔在桌上哪里还有陛下的影子。
  • 长指甲

    长指甲

    指甲长了,除了可以作为随手武器挠人外,要么当做突出的废骨头减掉,要么涂上妖艳的颜色显示自己多么的与众不同。如果你身处的环境不甚卫生,泥土灰屑便从容钻进你的长指甲里,令人咂舌。青春的生活里,有许多诸如长指甲般的选择或无奈,梦想,迷茫,追求,爱情,挣扎……没有人能左右。
  • 楚氏昭华

    楚氏昭华

    老话说的好,吃亏是福。上辈子楚蝉也这么认为,她性子温吞,老好人一个,受人挤兑也不会反抗。也不知是不是老天爷都看不下去了,所以让她死了又活了,还附带给她一颗聪明脑袋。
  • 诺贝尔

    诺贝尔

    诺贝尔是瑞典化学家、工程师、发明家。他利用他的巨大财富创立了诺贝尔奖,各种诺贝尔奖项均以他的名字命名。人造元素锘(Nobelium)就是以诺贝尔命名的。本书主要以其成长历程和人生发展为线索,通过日常生活中富于启发性的小故事来传达他成功的道理,尤其着重表现他所处时代的生活特征和他研究的艰难过程,以便对读者产生共鸣和启迪。本书包括人物简介、思想点拨、经典故事、人物年谱和名人名言等部分内容,具有很强的可读性、启迪性和知识性。