假如P=NP，世界将会怎样？

2009 年 11 月 17 日 / 88 条评论

在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？

已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。

一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。

Google在MIT发布的难题

2009 年 9 月 22 日 / 45 条评论

刚从cnPhil那儿看到一则有趣的消息：近日，Google Jobs在MIT校园内到处张贴着一份密码，企图在MIT校园里的一群变态中找出几个最变态的破密大牛。密码上面附文说，如果你能破解这份密码，你在Google会很有前途。据说，这份密码包含了一个Google Jobs的电话号码，解开密码的人可以通过此电话留下自己的个人信息。目前，还没有人破解出这段密码来。

趣题：平面图三染色的零知识证明

2009 年 9 月 17 日 / 12 条评论

在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？

IBM Ponder This史上最难谜题：给出谜底猜谜面

2009 年 4 月 9 日 / 25 条评论

2009年2月份IBM Ponder This的谜题可能是从98年谜题月赛开办以来最难的谜题。谜题发布一个月之后仍然没有任何人答对，主办人不得不宣布延迟一个月，并再三增加提示。最终，答对此题的仍然只有7个人。很久没有看到如此精彩的谜题了，有兴趣的网友不妨试一试。
题目非常有趣。传统的谜题是给出谜面求解谜底，但这个谜题则恰恰相反：下面这一串数字是某个问题的答案，你能猜出这个问题是什么吗？这串数字里有一个错误在哪里？

900F 80F0 8F00 80CA BE12 AA90 9400 0048 3E5B 8AC0 3400 00CB BC81 8A08 3C00 0050 BE43 00C0 3E00 A019 8059 BE13 2000 0092 BE9B 2A0B 2A00 8052 8841 04C0 3E00 840B 084B 0098 E000 8819 845A 8012 0300 0050 826F 0500 0600 846E 8264 0900 0A00 8065 0C00 0072 A054 8368 8569 4800 4400 8573 4200 4100 8349 8542 2800 2400 854D 2200 2100 9F00 E000 8888 8444 8000 0030 0DED 8222 0050 0060 8444 8222 0090 00A0 8000 00C0 0DED A000 8333 8555 4080 4040 8555 4020 4010 8333 8555 2080 2040 8555 2020 2010 8300 8500 8030 8050 0880 0840 8050 0820 0810 8030 8050 0480 0440 8050 0420 0410 8500 8030 8050 0280 0240 8050 0220 0210 8030 8050 0180 0140 8050 0120 0110 90F0 9F00 E000 8888 8444 8000 0003 0DED 8222 0005 0006 8444 8222 0009 000A 8000 000C 0DED A000 8333 8555 4008 4004 8555 4002 4001 8333 8555 2008 2004 8555 2002 2001 8300 8500 8003 8005 0808 0804 8005 0802 0801 8003 8005 0408 0404 8005 0402 0401 8500 8003 8005 0208 0204 8005 0202 0201 8003 8005 0108 0104 8005 0102 0101 9F00 8030 8050 8003 8005 0088 0084 8005 0082 0081 8003 8005 0048 0044 8005 0042 0041 8050 8003 8005 0028 0024 8005 0022 0021 8003 8005 0018 0014 8005 0012 0011 80FF 8F0F A333 8000 5000 0DED 8000 3000 0DED A333 C555 1800 1400 C555 1200 1100 8F0F A333 A555 1080 1040 A555 1020 1010 A333 A555 1008 1004 A555 1002 1001

密码学协议举例（五）：两个人能够在电话上打牌吗？

2009 年 2 月 20 日 / 47 条评论

密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题，两个人想通过一部电话打牌，但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议，并且保证游戏的公正性呢？
扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”，一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了，一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”，就是因为在棋类游戏中，双方的局面信息都是完全公开的。不过，打牌就是另外一码事了。你说你出方片7，我怎么知道你有一个方片7？事先发牌？那谁来负责发牌呢？怎样发牌呢？难道我告诉你“发到你手中的是两张3一张5一张8一张9”？这样一看，两个人“盲打扑克牌”似乎是不可能的了，要么需要借助道具，要么需要第三者的帮助。不过，运用密码学知识，我们可以设计一套扑克牌协议，该协议能够实现随机的、隐蔽的、公平的发牌，并且不需要其它东西的帮助。我们以一手五张牌为例，说明如何实现“两人各摸五张牌”的程序。