分享

呵呵，虽然本人对算法不是特别精通，但是最近花了挺多时间在P/NP问题，而且也想到了一个全新的思路，所以今天写一篇关于这个问题的blog，顺便也巩固一下我自己在这方面的认知，如果大家发现本文有任何问题，请指正。

什么是P/NP问题？

P/NP问题可以被认为说整个计算机科学最核心的问题，也是Clay七大千禧年大奖难题之一，首先将给大家介绍一下P/NP问题的四个最核心的概念：

1. NP：由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，也就是说，NP问题就是那些计算过程比较繁琐，但验证答案却很容易的问题，比如把整数44427进行因数分解，求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的，
2. P：其包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题，P问题也就是那些计算起来很容易，利用多项式算法很快能解决的问题，比如求若干个数的乘积。
3. NP完全（Complete）：NP完全问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合，而且NP完全问题之间是可以互相转换的，也就意味着只要一个NP完全问题能在多项式时间内解决，那么所有的NP完全问题都能在多项式时间内解决。
4. NP难（Hard）：在计算复杂度理论中，定义那些至少和NP里面最难的问题一样难的问题为HP难，也就是说，NP难的问题最差也是NP完全这个级别，比如寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是指数时间完全的。

而P/NP问题，就是论证P=NP还是P!=NP：如果P!=NP，也就是有些很容易得到验证的问题不容易被轻松地求解，这样我们的基于非常容易被验证的素数算法的密钥系统将保持完全，在影响方面，虽然这个世界本来是就是假设P!=NP，所以不会出现任何大的变化，但是整个证明的过程将会对其它一些问题的解决会有一定的启发作用，并对整个科技的发展有一定的推动；如果P=NP的话，每个答案很容易得到验证的问题也同样可以轻松求解，同时NP完全的问题也能被轻松地解决，而整个世界将会发生巨变，比如，所有的基于密钥的安全系统将失灵；算法的研究可能会转向围棋等NP难问题；数学证明可以完全交给计算机来处理；所有人工智能问题都将得到解决，并且机器人能完美模拟人类的行为。下图为P=NP和P!=NP被证明之后，计算复杂度领域新的概览：

图1. 概览

如果P!=NP，情况和现在差不多，NP完全和P都是NP的子集，但如果P=NP，P、NP和NP完全是相等，也就意味着所有NP完全的算法都能被快速地解决。

还有，为了方便介绍下面的，稍微介绍一些属于NP完全的算法，比如，著名的旅行商（Travelling Salesman）问题和哈密顿回路（Hamiltonian cycle）和用于测量布尔组合电路效果的布尔可满足性问题（Boolean Satisfiability Problem，简称SAT），下图一些NP完全问题及证明其为NP完全问题的变换流程图。在流程图中，箭头代表的是从何问题变换成另一问题的过程，要注意的是这张图并不代表这些问题的数学关系，事实上任两个本质为NP完全问题都可以以多项式时间变换，这图仅指示可以让研究者较为简单地变换问题的顺序，最源头的是SAT问题。

图2. NP完全问题

HP研究员的论文

图3. Vinay Deolalikar

最近，大家都知道HP研究院Vinay Deolalikar在美国时间8月8号发布一篇希望能证明P!=NP的论文，并在接下来的几天根据读者的反馈做了一定的更新，这里是最新版论文和概要，经过了包括陶哲轩、Richard Lipton和Timothy Gowers等多位顶级大师的审阅和在网上的讨论，发现Vinay Deolalikar的论文有一定的瑕疵，离证明P!=NP还有一定的距离，下面是陶哲轩的原话：“Ultimately, it seems that what Deolalikar has really proven is not that P != NP, but rather that pp != ppp,for which we have a simple half-page proof（最终，似乎Deolalikar真正已经证明不是P!=NP，而是只需半张纸就能证明的PP!=PPP）”

证明逻辑 

简单而言，他首先利用有限模型理论（finite model theory）中对多项式时间的描述，使用到了Moshe Vardi 和Neil Immerman的一个非常精彩的理论：在排序的结构中，一个关系可以定义为一阶逻辑公式加上最小定点（Least Fixed Point）算子，如果这个算子能在多项式时间内被计算。接着，他直接进攻SAT，希望能通过证明属于NP完全问题也是NP里面最难的问题之一的SAT不可能是P，来证明P!=NP，他的方式是：创建一个能编译SAT的排序结构，假设P=NP的话，为了迎合上面提到的理论，SAT会有特定的结构属性，而这些结构属性却和随机SAT的结构有关。总体来说，这个将有限模型理论和Random SAT模型串联起来的思路还是比较新颖。

主要问题 

对于论文的证明，许多人有不同的看法，但有一点非常关键，那就是Neil Immerman在Deolalikar对上面提到那个由他创建的理论的使用方式上面非常有异议。

我的一些想法

对于这个问题，我个人也已经有了一整套新的思路，但现在还成熟，计划在年内将paper投递给《中国计算机学会通讯》，是证明P=NP还是P!=NP，这个先保密。最后，和大家聊聊一下情怀，最近听闻美国这个季度的GDP增长为1.6，比较乏力，从这个数据我们可以得出，只要在今后十年我们能出现一家能超越微软/苹果/谷歌并能领导这个科技发展的企业，再加上我们庞大的人口基数，在经济总量上接近美国不是一个梦想，所以在这个巨大的浪潮当中，我觉得我们不应该选择抱怨、放弃或者求稳，而应该选择行动、坚持和冒险，因为挑战越大，风险越大，人生才会更好玩！

参考资料：

1. 惠普实验室数学家破解计算机科学最大难题
2. 假如P=NP，世界将会怎样？
3. P vs. NP，我们从过去的一周中学到了什么？
4. P/NP问题
5. Hamilton环多项式时间算法的说明
6. NP完全
7. Deolalikar P vs NP paper
8. The P≠NP “Proof” Is One Week Old
9. NP-hard

分享

分享

      刘辉现为美国华盛顿大学（University of Washington） 电子工程系正教授。刘教授1988年毕业于复旦大学电子系，1992年获得美国波特兰州立大学(Portland State University)电子工程专业硕士学位，并于1995年获得美国奥斯丁德州大学(UT Austin)电子工程专业博士学位。他于2009年获选美国电气电子工程师协会院士（IEEE Fellow），评语为： 对宽带蜂窝和移动广播的全球标准做出贡献（Citation：for contributions to global standards for broadband cellular and mobile broadcasting）。

      刘教授在学术杂志上发表了40多篇论文，并拥有30多项专利，他还是TD-SCDMA技术的主要设计者之一。他的研究方向包括无线网络，多媒体信号处理等。点击这里进入刘教授主页。他的联系方式为：

Hui Liu
Professor
Communications and Signal Processing
307P EEB
Box 352500
University of Washington
Seattle, WA 98195

分享

分享

【陈怀临注：从结构上讲，JNPR的M系列是其中低端路由器。M320意味这320Gbps的throughput，主要用在企业路由和中小数据中心方面；其Edge和Aggr的高端产品是Mx480，Mx960系列，对应CSCO的ASR1000和ASR9000，和大宋HW的NE40，NE80和ALU的7750等。】

分享

分享

【陈怀临注：打人只能显示内心的懦弱。强烈声援方舟子！越这样，越要坚决打假。BTW，谢所长，咱们虽然在IPV9上有一些分歧，但关系还是蛮好的呀，right？：-）。。。】
“今天（8月29日日）下午3点我约好辽宁卫视“王刚讲故事”的两名记者在北京住所所在小区的门口见面，然后一起走到附近一家茶馆（就是《中国企业家》详细描述过其位置的那家）接受关于李一事件的采访。5点左右，采访结束，我把两位记者送上出租车，转身才走两、三步路，只见一名男子突然窜到我面前，朝我的脸喷射气雾，我闻到一股刺激性味道，头晕脚软，几乎要倒下，我立即屏住呼吸，向路的对过跑去，后面另一个人追着我，手持铁锤要砸我头部，我拼命往前跑，此人在后面追，没能追上，就把铁锤向我扔出，连扔两次，第一次朝我的头部扔，没有砸中，我听到铁锤落地的声音，边跑边回头看了一下，此人又捡起铁锤扔过来，这次击中了我的腰部，流了一些血。我跑了有一两百米，歹徒未再追赶。我跑进小区后，报了警，警察很快来了。当时路边有一些人，警察立即去现场寻找目击者。做完笔录后，到附近医院验伤，除了腰部有两处破皮出血外，目前身体还未发现其他异样。

　　我本人没有私敌，这显然是某个被我揭露过的人雇凶报复，并已在我的住所附近踩点、守候多时，终于抓住了一个机会。至于是谁干的，我不好妄测，我知道的线索都已告诉警方。该案现在由石景山分局刑侦大队队长侦办，分局局长几次打电话过问，看来警方比较重视。希望能够尽早破案，并同时也侦破方玄昌遇袭案件。

”

分享

分享

转自cnbeta
新闻来源:Solidot
韩国的研究人员们建立了一个由端台式电脑组件组成的网络路由器，可以以创记录的速度传输数据。来自韩国高等科技研究院的团队创造的这款路由器，传输数据的 速度是每秒40千兆比特（gigabits ），比类似装置的前纪录快出许多倍。研究人员们使用的技术可能会带来很多方面的突破，包括在高性能路由器中使用廉价的芯片——如英特尔和Nvidia制造 的——以代替定制的硬件。 研究 人员们开发的软件还可以作为新网络协议的试验平台，有可能最终取代目前在互联网上运行了数十年之久的协议。

大多数路由器使用的是定制硬件， 在计算机网络之间传送数据。软件路由器利用普通硬件完成同样的任务，在软件中模仿硬件路由器的行为。像Vyatta生产的商业软件路由器一般只能达到每秒 3千兆比特的数据传输速度。这不够快，配不上一张典型网卡的最高速度，每秒10千兆比特。

“我们开始时只有一个保守的目标：第一个将电脑 路由器的速度实现每秒10千兆比特，然而，我们却达到了40，千兆”进行这项研究的实验室领头人文素（Sue Moon）说。她的学生韩祥进（Sangjin Han）和张基翁（Keon Jang）开发了一款名为PacketShader的软件，使得这一切成为可能。 PacketShader使用电脑的图形处理单元（GPU），来协助处理通过网络发送的数据包。

现代路由器早已不是简单的开关了，他们通 常在据包数通过时，以不同的方式对数据进行某种操纵。GPU是实现这一目的的理想工具，因为它们可以平行处理数据，这意味着它们可以一次处理多个数据包。 据文素说，在处理诸如认证或将数据包加密成数据流的过程中，GPU速度尤其快。当GPU着手这些任务时，它给了中央处理器（CPU）喘息的空间，去处理按 照自然顺序的其它任务，这样依次处理几个数据包可以发现异常闯入网络的企图。

伦敦大学学院（University College London）网络系统教授马克•汉德利（Mark Handley）指出，对于基本的数据包转发，计算机的CPU足够胜任，将GPU捆绑进来并没有优势可言。不过，他同意，GPU非常适合对数据包进行加密 或认证。

英特尔伯克利实验室的工程师吉安鲁卡•伊安纳孔（Gianluca Iannaccone）熟知PacketShader，他说，它可以将构成每秒1太比特软件路由器的实体机数量减少到他先前研究显示的需要量的三分之一。

“1太比特是企业级路由器的起点，而路由器是互联网的核心，”伊安纳孔说。他对名为RouteBricks系统的研究表明，未来路由器不 是现在这样专门的硬件，而是集群服务器上运行的软件作用。将足够的软件路由器绑在一起以每秒40千兆比特运行，你就可以得到一个本质上的太比特路由器。使 用这样的系统，将来某一天，路由器会完全在软件上运行。

“我们可以期望在此之上出现杀手级的应用软件，”另一位韩国高级科技研究所的教授 朴永苏（KyoungSoo Park）说，他参与了这个项目的研究。“在基于PC的软件路由器之上，你可以建立一个有趣的数据包或网络管理系统，这个系统不可能在硬件路由器上实施。 最终，你可以试验在今天互联网上还没有尝试过的新协议。

分享

分享

        智能手机市场随着iphone的出现以及Adroid的异军突起，出现了洗牌的征兆。全球手机市场和美国手机市场的趋势其实存在着很大的不同。在全球范围内，iphone攻城拔寨远没有美国市场那么得心应手。有意思的是，在美国商业界，global这个词通常表示包括美国市场的全球，而international通常表示除了美国以外的其他国家范围；这个心态和乾隆当年写给英吉利酋长的诏书里表现出来的心态很类似。

       全球智能手机市场销售，按平台排名，2010年第二季度和2009年第二季度对比如下（数据来源：Gartner）：

      而全球所有手机销售按平台排名对比如下（数据来源：Gartner）：

       不难看出，全球手机市场上，诺基亚和三星是稳定的状元和榜眼，“其他”手机品牌份额在上升，摩托罗拉和索爱在下降。在智能手机市场上，诺基亚和黑莓还是当之无愧的老大，但是其市场份额相比2009年二季度都有下降，下降的份额主要是让给了新秀Android。按照这个势头，Android超越老二RIM只是今年或者明年的问题。Symbian虽然市场份额一年内掉了十个百分点，但还是遥遥领先，老二老三加起来份额也没有它多。也许在未来两三年内，Symbian还能保持老大的位置，但是差距会进一步缩小，最终Android和Symbian会成为双寡头，RIM和苹果在三四名上搏杀，其他的估计都要打酱油了。

     我们进一步看看老大诺基亚2010年第二季度的损益表（数据来源：Yahoo Finance）。

     上表说明什么？诺西网络的收入占到诺基亚的三分之一了，但是总体一直在赔钱，在赔大钱。NAVTEQ的情况倒是在稳步好转，不过盘子太小。2010年二季度全球经济在放缓变差，也不可避免的体现在诺基亚的损益表上。手机设备服务的老大如何应对挑战者以及寻找新的增长点，弯曲评论将保持关注。

分享

分享

【陈怀临注：我个人认为创业的最佳年龄是23-30岁。然后其次是结了婚，但还没有孩子和房子。一旦过了这几个阈值，有一个好老婆就是最重要的了。另外，人生一世，Business不一定是Ultimate Goal。关键是要自己喜欢，要找到一个合适自己的位置在这个社会上。。。。。。总之，人生就那么几十年；Enjoy life。不要被太多的软（金，银，铜不等）手铐锁住心灵。。。另外不能急。任正非也是43岁时被人骗了单位的钱，据说是丢了工作，才在老婆逼迫下才创业，并一步步形成华为大业的。。。】

“创业是九死一生的事情。”清科集团总裁倪正东说。不经过创业的人不会懂。

但如今，太多创业传奇和创富传说蛊惑人心，每个创业者都想成为李彦宏、马云和马化腾，每个创业企业都想成为百度、阿里巴巴和腾讯。

然而，事与愿违。太多的风险投资，让他们变得更虚弱；太多的主张，让他们变得更狂躁；太快的烧钱，让他们变得更短命。

最近5年，在整个IT业界，最具创业激情和活力的领域当属互联网。从博客的一鸣惊人到电子杂志的横空出世，从 SNS的一夜爆红到视频网站的持续高烧，一个又一个互联网创新催生了数以万计的创业者，引来了以亿美元计的风险投资，也诞生了像方兴东、倪正东、庞东升、李想、李善友、汪东风等创业明星，以及各种明星企业。

5年，对于创业型企业而言是一个“死亡谷”，是企业必经的炼狱，大部分创业公司5年以后都不复存在。知名风险投资人查立，更是将这段时间的投资称为“死亡谷的蹦极”。

今天我们看到，以博客中国为代表的专业博客网站，以开心网为代表的SNS，以ZCOM为代表的电子杂志，以土豆、优酷为代表的视频网站，在经历了初创时期的跑马圈地、用户积累、人气笼络以及商业模式的探索之后，表现出这样那样的病相。

视频行业持续高烧。在酷6借华友世纪之壳上市之后，土豆拿到了第5轮共计5000万美元的投资。而整个独立视频行业的融资规模已经超过了5亿美元——让人瞠目结舌的数字后面，是被绑架的风险投资家们的孤注一掷。他们相信：视频是一笔值得投资的大生意；视频是烧钱的主；如果不接着烧钱，肯定没戏；烧最多的钱，保持领跑，就有希望——理性的投资家们疯狂的逻辑。

博客越来越被冷落，人气衰竭几乎难以逆转。在SNS、微博等更具交互性的新业务出来“抢人”的时候，即使是新浪、搜狐这样的大门户博客都不能幸免于人气徒降，那些专业的博客网站更是少人问津，加速地被人们遗忘——而失去了用户也就失去了盈利的基础，博客已是“日薄西山”。

电子杂志曾被认为是继门户网站、搜索引擎、博客之后的“又一把互联网之火”。如今，在烧掉了1亿美元之后，电子杂志几乎处于全行业休克状态。ZCOM办公室已经改换门庭； ZBOX倒闭，域名被卖；POCO转型为图片兴趣互动分享社区，整个行业尽显颓势。

SNS行业是最威武的“吸金王”，数年间竟然吸引了10亿美元的投资。但这个完全靠资本大量输血得以维生的行业，正面临失血过多的危险。排名靠后的蚂蚁网和360圈已经率先“血尽而亡”。即使挤入第一阵营，暂时无性命之虞的51、开心、人人等SNS网站，在盈利能力严重不足的情况下，如果烧钱越快，失血越快，也就死得越快。

其兴也勃焉，其亡也忽焉。

我们还会看到更多的创业公司深陷沉疴，还会看到很多“创业明星”变成“失败者”。但正如倪正东所言，我们的社会要容忍失败，要尊重创业者。因为创业实在是太难了，它会让你倾家荡产，它会让你卑躬屈膝，它会让你痛不欲生。

虽然创业失败了，但是创业家的精神不灭。

祝福他们。

分享