听从先知教诲，先行者自言自语的话俺一字一句全抄下来了，共6段5249个字啊，全手打还要校对真累死我啦！

deqiu

突然之间，游戏的加密技术发生了变化，谜题本身也忽然向几个方向发散：十六进制的字符、逆向工程、质数。蝉的图片变成了一种常见的主题，不禁令人想起著名小说家托马斯·哈里斯（Thomas Harris）《沉默的羔羊》一书中的飞蛾图片。

自从首次出现蝉的图片以来，相关猜测就一直层出不穷。有些人认为，这种图片可能只不过是种公关噱头，觉得是由一家公司开发的某种特别复杂的“另类实境游戏”（Alternate Reality Game），到最后的结果是为一部新电影或新车做宣传。

举例来说，微软就曾因其广受好评的“我爱蜜蜂”（I Love Bees）另类实境游戏而大获成功，这是该公司为宣传Xbox游戏《Halo 2》而在2004年推出的一种游戏，利用全球范围内的随机付费电话广播《魔兽世界》风格的广播剧，吸引玩家参与其中。

但就“Cicada 3301”而言，有些因素让事情变得复杂，可能令上述猜测难以成立。举例来说，这场游戏的组织者会积极地跟参与者进行互动。密歇根州一位昵称为“Wind”的女性参与者曾在多个网络留言板上参与这场游戏，但后来社区发现她故意散播虚假的线索。

deqiu

与这位散播假消息的女性参与者相比，其他一些人的行为则更加直截了当。在Pastebin网站上曾有人匿名发布了一个警告性的长帖，发帖者自称曾是“蝉组织”的一员，其身份是一名非英语国家的军官，受雇于该组织的“一名长官”。他在该贴中声称，“蝉组织”是一个“左翼宗教组织，但却伪装成一个进步的科学组织”，其成员包括“军官、外交官和学者，这些人都对当前的世界发展方向感到不满”。

deqiu

这位匿名发帖者还宣称，这个组织的计划是把人类变成尼采式的“超人”。他最后总结道：“这是一个危险的组织，他们所采用的方法很邪恶。”

由于并无其他线索能指向这个神秘组织的身份，因此许多人还猜测，该组织可能是被美国中情局（CIA）、英国军情六处（MI6）或美国国家安全局（NSA）聘用的，目的是寻找那些在密码破译方面极有才能的人，这种机构已不止一次使用类似的方法来寻找人才。

举例来说，今年9月份英国政府通讯总部（GCHQ）就曾发起过一场名为“Can You Find It？”（你能找到吗？）的测试，以便寻找最棒的密码专家。

网络谜团：一只令全球密码专家着迷的“蝉”

英国政府通讯总部的“你能找到吗？”谜题

deqiu

“二战期间，高度机密的‘政府密码学校’（Government Code and Cypher School）就曾利用《每日电讯报》上的填字游戏来为布莱切利公园（Bletchley Park，代指英国密码局）寻找人才。”吉罗格利说道。“但我不能肯定‘蝉组织’的背后是美国中情局或国家安全局。尽管最近发生了斯诺登事件，但这两个机构在安全问题上都是很小心的。”

其他机构才是幕后操纵者的可能性也无法排除。“在今天，计算机和数据安全的重要性比以往任何时候都要高。”吉罗格利说道。无线设备、手机以及亚马逊等电子商务网站的不断增加意味着，密码专家的重要性已经上升到了一个前所未有的水平。

吉罗格利指出：“就安全系统来说，其所使用的加密技术是否有效是非常重要的一个组成部分。而这就意味着，现在安全领域对密码专家的需求已经上升至史无前例的水平，而不再只是有情报服务就可以了。（‘蝉组织’的背后操纵者）也有可能是一家银行或是一家软件公司。”

埃里克森也同意这种看法。作为黑帽简报会议（Black Hat Briefings，保密的计算机安全会议，政府机构和公司可在会上听取来自黑客的建议）的常客，他知道有些组织会偶尔通过这种“钓鱼”的方式来聘用人才。但在他看来，种种迹象表明这是像Anonymous那样的黑客组织所采取的人才发掘措施。

当参与者解开在论坛上发布的信息密码以后，一条隐含信息会将其带到一个TOR（“洋葱路由”，是一种点对点的代理软件，依靠网络上的众多电脑运行的Tor服务来提供代理）地址；在指定数量的解密者访问这个地址以后，该网站就关闭了，只留下一条简洁扼要的信息：“我们想要的是最好的人才，而不是跟风者。”

被选中的少数人收到了电子邮件，但到目前为止还没人披露其详细内容。不过，据一名解密者透露，现在这些人已被要求在私底下解密。埃里克森并未被选中，他说道：“这对我来说是最虎头蛇尾的结局，我在TOR隐藏服务上注册电子邮件的时间太晚了。如果我的睡眠周期变一变，那么我认为我会是最先注册的人之一。”

几周以后，“蝉组织”在社交新闻站点Reddit上发布了一条新的信息：“大家好。我们已经找到了自己想要寻找的人，因此这段持续了几个月时间的旅程就此结束了。暂时而言是如此。”对于成千上万已经上瘾的解密者来说，这一天无疑来得过于突兀，但事实是这场游戏就这样忽然沉寂了下来。

但在今年1月4日，一条新的信息出现了：“大家好，又见面了。现在，我们又开始寻找高智商的人才了。”

然而，直到现在人们还是不知道“Cicada 3301”的幕后操纵者是谁，甚至不知道这场游戏的主要目的是什么。“但这正是其魅力所在。”埃里克森说道。“除非解决了所有问题，否则就没办法确切地知道这场游戏是为了什么。”

对埃里克森及其他被深深迷住的密码专家来说，2014年1月4日将是个大日子，因为在那一天，下一套谜题就将再次新鲜出炉。“或许到那时一切都将真相大白。”埃里克森咧着嘴笑道。“但从某种程度上来说，我对此持怀疑态度。”

deqiu

UVB-76：
UVB-76是俄罗斯一个位于4625 kHz（单边带）的神秘电台，收音机爱好者将其称为The Buzzer。它每天24小时发送向外发送单调的声音，每分钟重复约25次。UVB-76电台于1982年首次被观察到[1]，在少数情况下持续的嗡嗡声会中断，并出现由俄语播出的语音信息。[2]
正常传输
有许多关于此神秘电台的猜测，但是其真正目的和意义仍然未知。
该电台持续发送类似“嗡嗡”的声音，每次持续0.8秒，间隔1–1.3秒重复发送，每分钟可以重复21–34次[1]。每小时开始的前一分钟，持续的嗡嗡声会代替有间隔的声音，此声音会持续至一分钟之后，由间隔的嗡嗡声恢复。在格林尼治标准时间07:00至07:50，电台会使用低功率发送信号，似乎是在进行发射机常规检修。
故障
在这种情况下，在蜂鸣声的背后通常可以听到遥远的谈话声和其它背景噪音，这说明发出嗡嗡声的电台设备上有一个麦克风打开着，而且电台设备处在一个开放的喧闹环境中，而不是仅仅发送一段被重复播放的录音。在2001年11月3日时发生过一次这样的情况，可以听到一段俄罗斯语的谈话[1]："Я—143. Не получаю генератор." "Идёт такая работа от аппаратной."（“143，没有收到发生器（振荡器）。”“这里有一些硬件上的工作”）
语音信息
从UVB-76发出语音信息的情况是非常罕见的。自2010年的短暂停播之后，这个频率又重新开始播送信息。[3] 这些语音信息通常由俄语播出。[4] 在超过20年的观察中有七次此类信息被截获[5]

deqiu

在1997年12月24日格林尼治标准时间21:58，嗡嗡声突然停止并被短促的哔哔声取代，同时一个俄罗斯语男声宣布："Ya—UVB-76. 18008. BROMAL: Boris, Roman, Olga, Mikhail, Anna, Larisa. 742, 799, 14."[6]。同样的信息重复了数次，之后哔哔声以及嗡嗡声相继恢复。
2002年9月12日，UVB-76播出了类似的语音信息，但是声音十分扭曲而且难以理解，可能是声音源过于靠近麦克风头部。此次广播的部分信息被翻译为："UVB-76, UVB-76. 62691 Izafet 3693 8270."
2006年2月21日格林尼治标准时间7:57，UVB-76第三次播出了语音信息。同样，声音是非常扭曲的。全部信息被翻译为："75-59-75-59. 39-52-53-58. 5-5-2-5. Konstantin-1-9-0-9-0-8-9-8-Tatiana-Oksana-Anna-Elena-Pavel-Schuka. Konstantin 8-4. 9-7-5-5-9-Tatiana. Anna Larisa Uliyana-9-4-1-4-3-4-8."[7]这些单词在一些俄罗斯语字母表中可以找到，类似于NATO phonetic alphabet[8]。
在2010年之后，每隔几周就会出现一次人声，而且总在发生重大事件前后。2014年3月18日，在克里米亚投票加入俄罗斯之后不到24小时，电台发出了“T-E-R-R-A-K-O-T-A. Mikhail Dimitri Zhenya Boris （电台呼号）. Mikhail Dmitri Zhenya Boris. 81 26 T-E-R-R-A-K-O-T-A.”的人声。[9]
另外，这一电台会在数月或数年后重复同样的信号。2011年1月26日，电台发出了“ILOTICIN 36 19 69 46”的人声，在2011年5月11日，同样的声音再次响起。[9]
由UVB76发出的消息
发生日期        发生时间（UTC）        信息内容
1997年12月24日        21:58        180 08 BROMAL 74 27 99 14 Record Video
2000年12月24日        12:30        74 148 ANTIMONAT 26 37 09 31
2000年12月24日        12:45        61 21 ANTIMONAT 26 37 09 31
2002年12月1日        10:51        01 213 SKIF 38 87 23 95
2002年12月6日        07:03        28 138 KARIAMA 77 56 01 51 AGGRADACIYA 05 51 55 97 GLAShATEL' 76 78 55 08
2002年12月20日        18:43        45 359 DELMEZON 37 49 63 35
2003年1月15日        08:55        79 992 BONGU 99 23 77 68 BRONShshIK 71 17 57 70
2003年1月15日        15:30        03 517 KAMACIT 86 68 88 86
2003年1月16日        17:00        90 824 KROLIST 53 26 62 56
2003年1月16日        17:56        73 858 PODShEFNYJ 86 91 03 74
2003年1月17日        09:00        93 310 BILADIT 80 81 84 49
2003年1月17日        14:02        98 042 VYLENIE 36 20 09 83
2003年1月21日        09:52        80 516 GANOMATIT 21 23 86 25
2003年1月24日        17:25        07 526 RAZDVIZhOJ 18 47 27 96
2003年1月30日        08:04        01 851 AZOTIN 18 89 24 02
2003年1月30日        17:57        57 084 INICIAL' 76 16 56 79
2003年2月7日        09:03        15 286 ANGLEZ 51 09 98 29 BUShMAR 89 89 55 79 NOMINACIYa 74 97 16 56
2003年2月7日        09:34        85 596 KLASA 81 00 02 91
2003年2月11日        17:58        12 733 EDINENIE 67 79 66 32
2003年3月1日        10:30        60 130 VATRUH 58 89 54 54
2003年3月21日        10:28        95 695 TREZVENIK 16 24 54 27 TVORAIN 16 24 02 30
2003年3月24日        06:51        01 705 BRAMIRKA 18 49 70 39
2006年2月21日        7:57        65 265 FELAK 17 09 08 98 TEPEPShIK 85 59 75 59 TPLEABF 75 25 25 8 video
2009年9月29日        16:00        99 884 ASASDNYJ 42 67 28 17 Record
2010年1月25日        17:13        95 313 SUPRTKA 54 15 12 56 Record
2010年8月23日        13:35        93 882 NAIMINA 74 14 35 74 Record
2010年8月25日        06:54        38 527 AKKRECIYa 36 09 55 73 Record
2010年9月5日        13:39        19 703 PREGRADA 80 18 06 57 Record
2011年1月26日                ILOTICIN 36 19 69 46[9]
2011年5月11日                ILOTICIN 36 19 69 46[9]
2014年3月19日                T-E-R-R-A-K-O-T-A. Mikhail Dimitri Zhenya Boris. Mikhail Dmitri Zhenya Boris. 81 26 T-E-R-R-A-K-O-T-A.[9]
设备
该电台使用Molniya-2M (PKM-15)和Molniya-3 (PKM-20)发射机，和一个Viaz-M2备用发射机。发射机功率大约为10 kW，在格林尼治标准时间07:00至07:50，备用发射机功率为2.5 kW。天线形状是横向dipole VGDSh (Nadenenko)，高度约20米（66英尺）。

位置和功能
该电台的发射器2010年之前位于俄罗斯境内Povarovo郊外，Zelenograd和Solnechnogorsk之间，莫斯科西北部40公里处，靠近Lozhki村。该发射器位置直到1997年第一次语音信息发送才被最终确认。2010年，发射台从莫斯科附近被转移到了俄罗斯西部的普斯科夫州。[9]

不知是什么用意，一个网站声称该电台是“为了向莫斯科军方的军事单位和军队招募中心传递信息”，这个说法是未经证实的，并且无法解释此电台在播送一些单词和数字之前的15年中一直重复播送嗡嗡声。UVB-76在世界上被广泛认为是正在为间谍活动传送编码邮件【且最有可能是为俄罗斯间谍服务】，就像许多被伪装的数字电台占用着短波频率，许多电台发射机是一些国家的军队和情报机关安装的，虽然许多国家从来没有承认过这些电台的存在以及解释它们的用途。

deqiu

乍现灵光：
就是突然有了灵感的意思 ...

立体地画：
3D地画源自西方街头文化，英文：3D Street Painting 国内译为：3D地画、3D街头绘画、街头地画、3D街头地画、街头立体画、三维街头地画、街头三维地画、城市立体画、城市三维立体画等。
2005年由齐兴华首次引入中国。2009年《古龙今韵》入选第十一届全国美术展览，标志着街头地画正式被主流艺术所接纳。
3D立体地画是21世纪以后的地板艺术，是利用透视图手法将立体透视图画在地板上，并且与地板周遭景物结合，或者与行人作出有趣互动，又称为二次透视绘法。

2012年万氏兄弟在国内创作的《时尚之都、理想之城》3D立体地画作品获英国吉尼斯世界纪录总部官方认证，以148.63米成为世界上最长的3D地画。[1]

2013年12月15日，世界上最大的3D地画在深圳盐田蓝郡广场隆重揭开其神秘的面纱，并现场通过了吉尼斯世界记录的认证。这幅名为《蓝之梦》的3D地画长200米，宽6.1米，作品创作以海底世界等元素为主题，通过科幻手法，实现与海底景观、海洋生物、海底建筑的互动体验，以此传递海洋文化以及人与自然共存的理念。 [2]
重建立体感知
为了理解3D地绘的原理，我们首先需要了解人脑是如何产生深度知觉的。外部世界是三维立体的，但是它在我们的视网膜上留下的投影却是二维的。我们最终仍能感知到立体的世界，这是因为大脑会自动利用视觉信息中的各种深度线索，“重建”出立体的感知。


一般来讲，深度知觉的线索可以分为两大类。一类是单眼线索（monocular cues），这类线索通过一只眼睛的视觉信息就可获得，而另一类则需要双眼的配合。
最常见的单眼线索就是线条透视以及物体的相对大小。学过美术的同学对这种透视一定不会陌生：本身平行的线条，由于视角的缘故，会呈现出近宽远窄的样子，最终交汇于远方的某一点。原本大小相近的物体（例如两个一样的杯子，或者身高相仿的人），在视野中看起来大的那一个就会被感知为离我们较近，较小的那个则会被认为离我们较远。当一个物体遮住另一个物体时，我们也会认为前面的那一个离我们更近，被遮住的那一个则离我们更远。
此外，色调和光影也会带来重要的空间信息。一般来讲，高光的部分会被知觉为离我们较近，阴影的部分则会被认为为离我们较远。阴影也可以帮助我们感知物体的形状、体积、纹理等特征。另外，由于空气散射的存在，当物体离我们较远的时候，它的对比度和色彩饱和度都会下降，呈现出一种“雾蒙蒙”的样子。在很多3D电子游戏中，也会设置这样的“远距雾”（distance fog），以此来营造远景的感觉。
除了静态的信息之外，运动也会产生立体感。当我们处于运动状态时，较近的物体在视野中移动得较快，较远的物体则移动得较慢。例如，在坐车的时候，窗外的电线杆会一根根地快速闪过，远处的大楼则会慢慢挪动。
除了上面列举的这些，还有许多其它种类的单眼线索。这些线索的存在，使得我们即使闭上一只眼睛，也依然能感知到三维的世界。
除此之外，大脑在感知深度时，还会整合来自两只眼睛的信息，这类线索被称为双眼线索（binocular cues）。成年人两只眼睛之间约有6厘米的间隔，即使是来自同一光源的光线，它们在两眼视网膜上留下的投影也会存在细微差别。而大脑就会自动监测这样的差别，并据此做出深度判断。在观看较近的物体时，眼外肌也会帮助调整双眼，让视线汇聚到物体上，这时候，这种肌肉运动的信息也可以作为深度判断的依据。
骗过大脑的人造立体感
也许是由于深度感知的重要性，大脑对于各种线索的加工已经非常熟练，通过上面所说的种种线索，几乎一瞬间就可以建立起深度的感知。正是因为如此，大脑在立体感方面也很容易“受骗”，只要营造出恰好带有深度线索的视觉刺激，在平面上也可以产生种种逼真的3D效果。在各种视觉艺术中，都可以看到很多“欺骗”大脑产生立体感的技术，比如3D电影就借助偏光镜片人为地制造出了双眼视差，进而诱导出立体感。而绘画类的艺术作品则主要依赖单眼线索，通过各种技法表现和强化透视、光影等空间线索。
在这一点上，地绘和传统的绘画作品本质上其实是一样的。它的独特之处在于，作品不是正面悬挂于观赏者的眼前，而是“躺”在地面上，与观察者的视线存在一个角度。地绘艺术家会预先设计好一个位置，使得观察者站在这里观看时，图像恰好能在他们眼中形成理想的投影。此外，地绘作品还往往会与周围的环境相结合，这也进一步强化了现实感，产生艺术与现实交融的奇妙体验。不过，一旦改变了观测角度，就不会有这样完美的立体效果了。[1]
发展编辑
缘起
在二维平面上模拟三维空间效果一直是人类视觉艺术的焦点问题,尤其是自文艺复兴以来,解决该问题成为艺术进步和艺术史书写的重要标准之一，因此，文艺复兴及其之后的教堂壁画、天顶画、市政大厅、贵族寓所和别墅都成为极好的模拟场所。3D街头地画可看作这一艺术逻辑在当代的重要发展和延伸。所谓3D地画，顾名思义就是将画作展示于地上以求得立体的艺术效果，或直接以地面为载体进行绘画创作。3D地画，则将“艺术效果特殊化”的理念进一步发扬光大，它以室外地面为媒介，利用平面透视的原理，制造出视觉上的虚拟立体效果，令参观者有一种身临其境的感觉。3D地画中的景物立体、细腻、逼真，往往能达到以假乱真的艺术效果。
严格意义上的3D地画发源于国外，有着长达二十多年的历史，已经发展成为一种成熟的艺术表现形式。它秉承后现代绘画理念，诞生于西方大众文化的语境中，最初是西方先锋街头艺术家表达自我、彰显个性的一种方式，它创作成本低廉，受场地限制程度低，发挥的自由度大，因此从诞生之日起就成为一些西方草根艺术家所钟爱的艺术形式；又因为它颇具娱乐精神与诙谐效果、易于与流行文化元素相关联，加之场地开放，创作与展示过程都是在露天完成的，打破了民众与传统绘画艺术殿堂的隔阂感，因此很容易受到参观者的认同、喜爱与欢迎。近年来涌现出一些致力于3D街头地画创作的艺术家。如丹麦艺术家JulianBeever，就是其中的佼佼者。
传入中国
2005年，国内首位3D地画艺术家齐兴华（Qi Xinghua）将3D地画艺术引入中国，他的首张3D地画《漩涡》（原名：与一个坑）在--北京（北京大学、北京鼓楼、清华大学、颐和园、圆明园、）等地都做过现场展示，并引起了一定规模的轰动效应。近两年他的3D地画《古龙今韵》《杨浦往事》《源》又参加了北京奥运会和上海世博会的展览，2010年5月16日，齐兴华的3D立体地画作品《唐吉可德》经英国吉尼斯世界纪录总部官方测量认证，以535.3㎡成为当时世界上最大的3D立体地画，之后又3次刷新或打破吉尼斯3D绘画世界最大，最长世界纪录。和在网络等传播媒介的积极作用下，3D地画已渐渐为大众所熟悉和接受，具备了一定的认同度与美誉度，但总体来讲这种艺术形式在中国仍处于方兴未艾的阶段，大众对这种艺术形式仍然具有强烈的好奇感，对这种新兴的艺术形式抱有浓厚的兴趣。

deqiu

P与NP：
P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P=NP?）。

P=NP
复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：

P和NP相等
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[1] 对于正确的解答，有一个1,000,000美元的奖励。

NP-完全问题（或者叫NPC）的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的（确切定义细节请参看NP-完全理论）。计算机科学家现在相信P, NP，和NPC类之间的关系如图中所示，其中P和NPC类不交。


假设P ≠ NP的复杂度类的图解。如P = NP则三个类相同。
简单来说，P = NP问题问道：如果实然问题的正面答案可以很快验证，其答案是否也可以很快计算？

这里有一个给你找点这个问题的感觉的例子：

给定一个大数Y，我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因数。 答案是肯定的，虽然手工找出一个因数很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611"，则我们可以很快用一个除法来验证。 验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。 所以我们的结论是，给定正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。

虽然这个特定的问题，最近也被证明为在P类中（参看下面的关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类P。

像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP = FNP）是等价的。

学术定义
更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。

现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多nk步之内产生“是／否”答案（其中n是w的长度而k不依赖于w）。进一步假设

w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。
则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。）

NP完全
要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行推销员问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被证明为在P内，则P = NP。旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

更难的问题
虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是指数时间完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定Presburger算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少22cn的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题。它们无法在任何给定时间内解决。

P真的容易处理吗？
上面所有的讨论，假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：

它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是指数时间的），但是对于n取值直到几千时还是很容易处理的。
它忽略了指数的大小。一个时间复杂度n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间层次定理）。一个时间复杂度2n/1000的问题不属于P，但对于n直到几千还是容易应对的。
它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP，BPP）。
新的诸如量子计算机这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
计算机科学家为什么认为P ≠ NP？
多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步地，P = NP这样的结果会导致很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 反NP和P = PH。

也有这样论证的：问题较难求解（P）但容易验证（NP），这和我们日常经验是相符的。

从另一方面讲，某些研究者认为我们过于相信P ≠ NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明：[1]

“        倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。……费马最后定理的解决也显示非常简单的问题可能只有用非常深刻的理论才能解决。        ”
— Moshe Y. Vardi，莱斯大学
“        过分依赖某种投机的猜测不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。        ”
— Anil Nerode，康奈尔大学
关于证明的难度的结果
虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的，但是还有一些形式化的结果证明为什么该问题可能很难解决。

最常被引用的结果之一是设计神谕。假想你有一个魔法机器可以解决单个问题，例如判定一个给定的数是否为质数，可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论带来的后果是，任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。

如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。[2] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。

这实际上也是为什么NP完全问题有用的原因：若对于NP完全问题存在有一个多项式时间算法，或者没有一个这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决P = NP问题。

多项式时间算法
没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如下面的算法正确地接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当P = NP。

  // 接受NP完全語言的一個算法子集和。
  //
  // 這是一個多項式時間算法當且僅當P=NP。
  //
  // “多項式時間”表示它在多項式時間內返回“是”，若
  // 結果是“是”，否則永遠運行。
  //
  // 輸入：S = 一個自然數的有限集
  // 輸出："是"如果某個S的子集加起來等於0。
  //         否則，它永遠運行沒有輸出。
  // 注意:  "程序數P"是你將一個整數P寫為二進制，然後
  //         將位串考慮為一個程序。
  //         每個可能的程序都可以這樣產生，
  //         雖然多數什麼也不做因為有語法錯誤。
  //         
  FOR N = 1...infinity
      FOR P = 1...N
          以S為輸入運行程序數P N步
          IF程序輸出一個不同的整數的列表
              AND所有整數都在S中
              AND整數的和為0
          THEN
              OUTPUT "是"並 停機
若P = NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。

可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：

          IF程序輸出一個完整的數學證明
              AND證明的每一步合法
              AND結論是S確實有（或者沒有）一個和為0的子集
          THEN
              OUTPUT "是"（或者"不是"如果那被證明了）並停機
逻辑表述
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性二阶逻辑来表达—也就是，在关系、函数、和子集上排除了全称量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”

花絮
普林斯顿大学计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[2]

康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：[3]

反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到了矛盾。

xialei_026

楼主应该是先截图，然后照着打字的吧？

Wind-9

太专业了，先顶再看！

deqiu

xialei_026 发表于 2018-2-13 07:34
楼主应该是先截图，然后照着打字的吧？

不是的，我做完这个伊述盔甲的隐藏作务后，发现已无法再次触发对话，又想把这些话记录下来，就在网络上找相对应的视频，找到了然后对着大神玩的繁体字版本的视频并切换到繁体字输入法用记事本抄下来，再用word2016转换成简体，然后上传到这的。

deqiu

Wind-9 发表于 2018-2-13 13:05
太专业了，先顶再看！

嗨：来自西西里的教父你好啊！没有想到在游侠网能看到你，此刻我心是如此的激动竟流下了感动的眼泪！

xialei_026

deqiu 发表于 2018-2-14 01:26
不是的，我做完这个伊述盔甲的隐藏作务后，发现已无法再次触发对话，又想把这些话记录下来，就在网络上找 ...

那真是辛苦你整理了。

xialei_026

话说关于人有九个灵魂那里，其实中国古代也有三魂六魄一说，看来这点上还挺有共识的。

mcsgood

真的是太强的没有，楼主这是给大家搞了个研究生级别的科普知识讲座。

什么也不想

这个不错，虽然看不懂。哈哈

deqiu

什么也不想 发表于 2018-2-17 20:45
这个不错，虽然看不懂。哈哈

过奖了。

ljm3139

6666收藏起来慢慢看