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

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

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

Read more…

    偶然看到这个网页，很是受启发，然后自己也没事干，一个人躺在床上想了很多。

 
昂贵而奢侈的房间
    制造一个房间将变得非常的昂贵，也将变得非常非常奢侈。为了建造一个1000维的立方体空间，你需要在2000个方向上各修建一个999维的墙，即使墙的“厚度”很小很小，这也需要耗费大量的人力、物力和财力。同时，这样的房间也将非常非常非常大。假设1000维空间中的人是一个边长一米的超立方体，边长两米的超立方体房间里可以容纳10^300个人。当然，也许有人会问，为什么不把房间边长定小一些呢？如果房间边长仅有1.01米，容量也超过20000了啊？其实，房间容量大了没有任何意义，人多了照样挤不下。正如把一个单位大小的三维立方体放进边长为1.5米的三维立方体盒子中一样，虽然余下的空间超过了两立方米，但这点空间仍然不可能挤下哪怕再多一个的单位立方体。

 
死一般的世界
    不要对高维世界抱有任何美好的幻想。1000维世界里是一片黑暗的。在1000维世界中，发光体再也牛B不起来了。半径为2的超球体，体积是单位超球体的10^300倍；因此随着与光源的距离的增加，照度以难以想象的恐怖速度垂直递减。类似地，1000维世界也是无声的。要想让声音传到10米外的地方，需要耗费的能量是一个天文数字。
    在这样的世界中，生物将无法进行远程交流，甚至不会进化出视觉和听觉能力。一切社交行为都是以直接接触的形式发生的。另外一种可能是，当被动接收外界能量不可能实现时，生物将进化出一种主动探测外部世界的能力。生物可以发出一种集中程度高、不易向四周弥散的能量束，该能量束能够沿原路返回，使得生物能定向地获取外部信息。
    正如宇宙射线、暗物质、反物质等一些我们（或许是因为缺少某种感觉器官而）感受不到，但事实上确实存在的东西一样，1000维世界中的科学家猜想有光源、声源等自然能量产生。他们投入了大量精力，耗尽了身边可用的资源，企图创造出一个可测量的尺度下的能量源。发现自然的光源和声源将成为物理学界的前沿科学，或者被宗教利用，成为一种具有蛊惑性的仪式。

Read more…

    前两篇文章中，我们提到了两个用杠杆原理解决数学问题的例子。这篇文章将从另一个物理领域出发，探索光学的一个重要原理与几何极值问题的关系。
    物理学的美不仅仅表现在简洁的公式上。我们还惊奇地发现，很多物理现象都是按照使某个变量达到极值的方式发生。一个典型的例子就是Fermat原理，它指出了光的传播路径的一个重要规律：光总是沿着所花时间最短的路径传播。这里我们将简单介绍一下Fermat原理，该系列后面的文章里将会用到这一原理。
    Fermat原理俗称“最快到达原理”、“最小时间原理”，意思是光线传播的路径总是满足这样一个规律：它总能使光在最短的时间内到达目的地。这个原理完美地统一了直线传播定律、反射定律和Snell定律，解释了为什么光线总是沿直线传播，为什么入射角等于反射角，以及光线在不同介质间传播为什么会发生折射现象。
    在Ted Chiang的著名科幻小说The Story of Your Life里有这样一段形象的描述：

    “好，这是一条光线从空气射进水中所走的路线。在碰到水面前，光线沿着直线前进；水有不同的折射率，所以光改变了前进方向。你以前听过这个，对吗？”
    我点点头，“当然。”
    “现在关于光所走路线有个有趣的性质。这条路线是这两点之间可能的最快的路线。”
    “又来了？”
    “想象一下，光线沿着这条路线前进。”他在图解中加了条虚线。
    “这条假想中的路线比光实际走的路线要短。但是光在水中前进的速度比在空气中小，而这条假想的路线的很大一部分是在水中的，所以光沿着这条假想的路线所花的时间要比沿着实际路线要长。”
    “好，我明白了。”
    “现在想象一下，假设光沿和另一条路线前进。”他画了第二条虚线。
    “这条路线减少了在水中的比例，但总长增加了。光沿着这条假想的路线所花的时间也要比沿着实际路线要长。”
    Gary放下粉笔，用蘸着粉笔屑的手指指着黑板上的图解，“任何假想的路线都比实际的要花更多的时间。换一句话说，光线走的路线是最有可能走得走快的一条。这就是Fermat定理的最小时间原理。”

    你发现Fermat原理有什么奇怪的地方了吗？你是不是感觉Fermat原理很诡异，但自己也说不清楚到底是为什么诡异？仔细想想你会发现，“最快到达”这种原理显然是不符合我们的行为方式的：假如我是光，我的传播规律是“最快到达”，但此时我要传播到哪里还不知道呢。Ted Chiang的小说对此也做出了详细的描述：

    “然而我仍要问你关于Fermat定理的东西。它的一些东西让我感到奇怪，但我不能正确指出那是什么。它只是不像是物理法则。”
     Gary的眼睛闪了一下，“我打赌我知道你想谈什么，”他用筷子把锅贴夹成两半，“你习惯于用起因和结果来思考折射：光照到水面上是起因，方向的变化是结果。但Fermat定理听上去很古怪，因为它以目的的形式来描述光的行为。它就像是光线的指挥官，‘你应该将抵达目的的时间最小化或最大化。’”
    我想了一下，“继续说。”
    “这是物理法则的一个老问题。人们在17世纪Fermat定理第一次成形时就一直在谈论它。Planck写了好几卷。本质是，普通的物理法则的表述是具有因果关系的，而像Fermat定理的可变法则具有目的性，几乎是目的论。”
    “嗯，这样解释道挺有趣。让我想一下。”我拿起一支标签笔，在餐巾纸上画了幅图解，就是Gary在我的黑板上画的那幅，“好，”我想我很大声地说道，“那么让我们假设光的目的是要沿着最快的路线前进。这样的话，光如何走呢？”
    “好吧，假若按人类行为学来说，光得检验每条可能的路线并计算每条得花多少时间。”他从盘子里戳起最后一块锅贴。
    “那样做的话，”我继续道，“光线得知道目的在哪儿。假如目的地在某某其他地方，最快的路线就会不同。”
    Gary再次点点头，“完全正确。‘最快的路线’的概念是无意义的，除非有特定的目的地。计算沿着一条假想的路线需多长时间也需要关于在这条路线上有什么东西的信息，比如水面在哪？”
    我继续看着纸巾上的图解，“在光开始移动前，它得事先知道所有这一切，对吗？”
    “这样说来，”Gary说，“光线不能沿着老路前进，然后再在后来返回。因为引起这样行为的路线不是最快的。在一开始光就已经做好了全部的计算。”
    我心中暗想，在光线能够选择它移动的方向前，它已经知道它最终会在那里结束。我知道这让我想起了什么，我抬起头看着Gary，“这让我困扰。”

  
    上面的论述似乎很抽象。我们来看一个实际的数学问题。这个问题有点怪，和其它的问题很不一样。给出一个点A，给出两个圆O1、O2，再给定O1上的一点B，问O2上是否存在一点C，使得B点的位置恰好能让AB+BC达到最小，也即对于O1上异于B的任一点B'都有AB'+B'C > AB+BC。你一时间可能找不到这个点C，这很正常，但光可以立即找到这个点C。因为从Fermat原理的角度看，光的思维方式是“逆向”的，这个别扭的题目正好顺应了它的思维方式。只要沿AB发射一条光线，在圆O1表面上发生反射后的光线与O2的交点即为点C。因为，A->B->C这条光路符合光的传播性质，这条路径是所有经过O1上一点到C的路径中最短的一条，其它所有的B'都会使光程增加。事实上，光就有这种神奇的本领：不管之前有过多少反射点，有过多少折射点，这条光线今后传播到的每一个点都满足这种无比别扭的“以它为终点则前面的定点均已达到最优”的性质。对于光来说，这是顺理成章的事；但从我们的角度来看，还没到目的地便能确保路径最优是很不可思议的。我们会习惯性地认为，光从A点出发往B走之前必须得先知道它的终点是C，然后才会知道B可以使光程最短，因此它才会往B走。这是明显有悖于我们熟知的因果关系的。或许说，这个世界本没有什么因果关系，仅仅是因为人类的思维被禁锢在了因果链式思维中？

    接下来，我们举两个火星例子。两个都是经典的小学奥赛题。
  
    问题1：给定直线l同侧的两点A和B，在直线上找一点C使得折线ACB最短。
    问题2：角ABC内有一点P，请在AB上找一点M，BC上找一点N，使得三角形PMN的周长最短。
    类似的问题还有很多。很多这类几何极值问题都和Fermat原理有直接

    今年恰逢PKU数学文化节十周年，其间开办的很多讲座我都去了。去听讲座的人好像都是数院的，我恐怕是唯一一个中文系的。考虑到我和中文系的MM没有共同话题，因此每一次听讲座时我都会顺便四处打望，看看有没有数院的美女，下来可以和她“交谈”一下。有趣的是我的做法与常人所想的恰好相反：据说数院的已经盯上中文系的MM了，而我一个中文系的竟然反过来去找数院的MM。
    昨天有一个关于非欧几何的讲座，这是目前所有的讲座中最为精彩的一次。讲座里提到了Poincaré的一个双曲几何模型，感觉非常有意思，在这里和大家分享一下。
    在所有的双曲几何模型中，Poincaré的圆盘模型可能是最有趣的一个。这个双曲世界存在于一个有限的平面区域里，整个世界限制在一个单位圆的范围内。这个世界中有两个最重要的物理定律：一，假如某物体X离原点O距离为d，那么该物体的温度为1-d^2；二，物体的大小与温度成正比。这样，假如某个人从这个世界的中心走向边缘，那么他的温度会从1慢慢变成0，同时整个人慢慢变小。他自身大小改变的同时周围的物体也等比例地放大或缩小，而这个世界里的人视野有限，看不见远处的东西，因此他不会觉得自己变小了或者变大了。因此，在这个世界里，物理学家们能够很轻易地发现第一定律，但要发现第二定律则非常具有挑战性，探索第二定律的过程必然很曲折，并且很可能出现哥白尼时代的故事。
    对于我们来说，这个世界是有界的；但对于这个世界中的人来说，这个世界是无穷大的。因为离原点越远，人就越小，于是相对来说他们所看到的空间也就越大。当人的位置趋于边界时，物体大小趋于0，此时的空间将变得无穷大，因此这个世界中的物体永远无法到达边界。同时，离原点越远的话越接近“绝对零度”，这将非常不适宜生物的生存，因此人们大多居住在原点，离原点越远城市规模越小，更远的地方则完全没有开发过，只适合于疯狂的冒险家进行极限运动。于是这个世界中的物理学家很自然地得到这个结论：世界是无穷大的。
    下面就神奇了。现在，考虑某个人想从A点走到B点。如果按照红色的线段直直地走过去，所走的路程并不是最短的，因为这条路线离原点较远。聪明的人会发现，我先往原点方向走一点，然后再到B点去，这样走的路程更短一些。我们猜想，最短路线很可能是一条偏向于原点的弧线（就好像原点把直线段“吸”过去了一样）。之所以产生这种奇怪的现象是因为，离原点越远物体就越小，人的步子也变小了，相对来说实际空间就变大了。因此，对我们来说距离相等的两点，对他们来说离原点越远其实际距离越大。因此，我们有必要重新定义这个双曲世界中“距离”的概念。由于物体大小与1-d^2成正比，因此我们可以定义，如果在离原点距离为d的位置上有一个充分小的位移，在我们看来距离为Δx，那么在这个世界中的实际距离就是Δx/(1-d^2)。这样就可以算出，从A到B的最近路线是一条垂直于边界的圆弧（蓝色的那条）。于是在这个世界中，“直线段”已经不再是我们熟悉的直线段了，而是一条条的弧线（还包括整个圆的直径）。而我们眼中的直线，在他们看来就是曲线。
      
    这个世界中的几何满足欧式几何的前面四个公设，但不满足第五公设。比如，两点确定一条直线，因为过两点的圆弧只有一条垂直于这个世界的边界；而直线可以无限延长，因为离边界越近两点的实际距离越大，你永远走不到尽头。但是，这个世界不满足第五公设。从图2可以看到，过一点可以作无数条直线不与已知直线相交；从图3可以看到，三角形的内角和小于180度。下面这幅图片可以帮助你更好地理解这个双曲模型。这是该平面上的一个三角形剖分，里面的所有三角形都是等边三角形，而且所有这些三角形都是一样大的。你可以看到7个等边三角形共用一个顶点，这说明三角形的内角和小于180度。

    另外值得一提的是，这个构想很适合写成一篇科幻小说。记得大刘的那篇科幻吗？一群电子器件诞生在某颗星球的内核，然后探索物理定律，历经重重困难，最终冲破了它们那个世界的“天然外壳”，看到了外面的世界，并相信我们整个宇宙也处于一个更大的星体内。这个双曲几何模型也很适合写出这样的小说来，比如以物理史书的方式叙述从古至今若干个传奇人物的故事，讲述他们是如何从一些奇怪的现象出发，通过各种试验证明自己的猜想，顶住社会各方面的压力，执著地探索宇宙的奥秘。小说中的人物可以带着读者一起进行探索，最后才告诉读者这个宇宙的本质是什么。

Matrix67原创
转贴请注明出处

    Flatland是一部巨经典的科学幻想小说，小说里构造了一个全新的世界──这个世界是二维的！整个小说分成两个部分，前一部分系统地描述这个二维世界，包括自然状况、居民生活、政治历史等等。真正有趣的事情发生在后一部分里，这里不同维度的世界之间发生了碰撞——二维世界中的主人公拜访了一维世界，同时又接触到了一个全新的三维世界。当他在他的世界传播三维思想时，整个世界大乱，哥白尼时代的那段故事再次发生。
    Flatland: The Movie是由此改编的一个动画短片，整个电影大约30分钟。官方网站上已经放出了电影的预告片，看起来非常有意思：

下面是一个两分多钟的片段：

原版小说：http://xahlee.org/flatland/index.html
陈忱译《神奇的二维国》：http://www.matrix67.com/data/flatland.html
官方网站：http://flatlandthemovie.com/
imdb链接：http://www.imdb.com/title/tt0814106/

现在，你可以在官方网站上订购学校教育专用的特别版DVD，价格是120美元；30美元的个人版DVD还要过几个月才能订购。