N = NP ？
作者：admin，2009年十一月12日 9:23 上午，分类：数学, 数据结构算法, 读书
终于捡到一个时间来写这篇文章，其实我对p和np也不是很了解，只是觉得学计算机的起码应该知道，np问题应该算是计算机科学中的未解决的问题，关于n=np 也是一个未知的问题，Clay数学院评出的七个悬赏百万美元的难题。简单的讲p就是我们能在多项式时间内解决的问题？例如一些排序算法，初等的一些数学运算，p就是polynomial ，计算机科学里的算法复杂度是O(n),O(n^2)等都属于p问题，而np问题则是不能在多项式时间内解决的为难题，它是有20世纪70年代，数理逻辑领域两位计算机科学家的发现，Stephen A. Cook 和richard karp的论文，许多类型不同的问题抽象的逻辑问题其实是同一个问题伪装成不同的形式，np是一个世界之谜，当我们有限的心灵面对宇宙成指数，也许是比指数更高级的一个运算的运算的复杂度增长时，我们如何应对，为什么我们无法预测未来，变量太多，导致我们的运算成告诉增长的苦难，简单如天气预报来说，计算机发展十年天气预报才能多预报一天，但是预报的也不是百分之百的准啊，大家都会深有体会，世界时一个混沌中，在其中，我们和合自然抗衡还差很远。
在生活工作中，我们是在solving problems，而且一般我们处理的问题一般也是p问题，很简单的能把它解决，复杂性能不算太高，但是如果别人给你出一个问题说给我算一下10的100次方个素数是多少？你会傻眼的，为什么？？很简单的问题的复杂度增长的太快，一个简单的例子是我们高中在学等比数列时候的一个小故事，向国外索要粮食，以2为底数，可见都速度惊人？何况以别的呢？现实生活中以指数式增长的例子比比皆是，《数字追凶》记得描述过一个这样的案子，甲流如果不控制，可以想象其传播速度会有多快？在有一个例子是计算机安全领域的一些加密算法，很显然我们如果采取逐个坚持，所谓的暴力破解去解rsa，des算法相信还是很困难的，但是给你密钥，验证就可以在多项式时间内完成。可见np问题是非确定计算模型下易验证的问题，np完全是一类看似不相关的问题，可以最终化解成一类问题，如果解决了这样一类 问题，这整个问题链条都可以迎刃而解，如果a问题能化解为b，b能化解为c，c能化解为d等等，这解决了最底层的则整座大厦将可以击破，著名的np完全问题 旅行售货员问题，哈密顿问题，相信学计算机的都应该学过，这些问题会出现在《离散数学》，《算法分析》课程中，如果城市有限，我们可以把旅行售货员去过的地方做成图，或者画一个树，画出所有可能到达的分支，利用回溯法即可解决问题，但是如果他要去一万个城市呢？复杂度可想而知，但如果知道了，我们可以轻松的验证，许多问题都属于此类，如果我们找到一个通用的方法解决np问题在多项式时间内，即n=np，这我们的则没有安全，估计也到了大同世界，只要有密码的地方我们可以运行下计算机，轻松破解，而不比等千万年。例如我们的rsa加密算法利用的是大整数的分解的复杂度，迷宫也是一个np问题，世界就是一个错综复杂的迷宫。
下图是wiki上的np，p问题的所属列表。
说到问题的转化和分解，想起编译原理课程中讲过的一些状态图，图灵机等，事物的转化状态，看似复杂的理论，起最终的解决可以固定到一些模式上，例如经常提到的狼和白菜和羊过河问题，这样的问题，可以通过分析状态，画出状态。把所有的解化解成固定的模式。
在np完全问题上，可喜的是今年第25界计算几何年会我国复旦大学的学者提出 ，”最小曼哈顿网络问题是一个NP完全问题“，获得最佳论文奖，np完全还是很多的存在在现实中。 附件为他们的论文。scg
参考：
1 http://web.mit.edu/newsoffice/2009/explainer-pnp.html
2 计算机算法设计与分析
3 推理的迷宫