這個是大件事啊

　　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.