P≠NP，一个简洁的论文标题，或许预示着七大世界数学难题之一的P问题(多项式算法)对NP问题(非多项式算法)终于有了答案。据英国《新科学家》杂志网站8月11日(北京时间)报道，美国惠普实验室的数学家维奈·迪奥拉里卡已经于6 日提交了关于论证该问题的论文草稿，如果此答案被证实无误，那么他将获得由美国克雷数学研究所提供的100万美元奖金。
P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。有些问题计算起来很容易，利用多项式算法很快能解决，比如求若干个数的乘积，这类问题被称作P问题；另一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的，这类问题就被归为NP问题。
因此，如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。
而现在，迪奥拉里卡围绕一个众所周知的NP问题进行论证，给出了P≠NP的答案。这就是布尔可满足性问题(Boolean Satisfiability Problem)，即询问一组逻辑陈述是否能同时成立或者互相矛盾。迪奥拉里卡声称，他已经证明，任何程序都无法迅速解答这个问题，因此，它不是一个P问题。
如果迪奥拉里卡的答案成立，说明P问题和NP问题是不同的两类问题，这也意味着计算机处理问题的能力有限，很多任务的复杂性从根本上来说也许是无法简化的。
对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的；但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题(Travelling Salesman Problem)，即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有计算机程序可以迅速给出这个答案。
迪奥拉里卡的论文草稿已经得到了复杂性理论家的认可，但一周后公布的论文终稿还将接受严格的审查。
附：
http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
P ≠ NP? It\'s bad news for the power of computing
- 14:35 10 August 2010 by Richard Elwes
- For similar stories, visit the Computer crime Topic Guide
Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply P ≠ NP.
This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute\'s seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.
The P versus NP question concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly – in technical terms, the running time is proportional to a polynomial function of the input size – and these tasks are in class P.
If the answer to a task can be checked quickly then it is in class NP.
So if P = NP, every problem that can be checked quickly can also be completed quickly. That outcome would have huge repercussions for internet security, where the difficulty of factorising very large numbers is the primary means by which our data is kept safe from hackers.
Ingenious argument
But Deolalikar says that\'s not the way it is. His argument revolves around a particular task, the Boolean satisfiability problem, which asks whether a collection of logical statements can all be simultaneously true or whether they contradict each other. This is known to be an NP problem.
Deolalikar claims to have shown that there is no program which can complete it quickly from scratch, and that it is therefore not a P problem. His argument involves the ingenious use of statistical physics, as he uses a mathematical structure that follows many of the same rules as a random physical system.
If the result stands, it would prove that the two classes P and NP are not identical, and impose severe limits on what computers can accomplish – implying that many tasks may be fundamentally, irreducibly complex.
For some problems – including factorisation – the result does not clearly say whether they can be solved quickly. But a huge sub-class of problems called NP-complete would be doomed. A famous example is the travelling salesman problem – finding the shortest route between a set of cities. Such problems can be checked quickly, but if P ≠ NP then there is no computer program that can complete them quickly from scratch.
Complexity theorists have given a favourable reception to Deolalikar\'s draft paper, but when the final version is released in a week\'s time the process of checking it will intensify.
