P VERSUS NP
Note, however, that many solvable problems are believed to have the property
that no algorithm with polynomial worst-case time complexity solves them, but that a solution, if known, can be checked in polynomial time. Problems for which a solution can be checked in polynomial time are said to belong to the class NP (tractable problems are said to belong to class P). The abbreviation NP stands for nondeterministic polynomial time. The satisfiability problem, is an example of an NP problem—we can quickly verify that an assignment of truth values to the variables of a compound proposition makes it true, but no polynomial time algorithm has been discovered for finding such an assignment of truth values.
(For example, an exhaustive search of all possible truth values requires 2n bit operations where n is the number of variables in the compound proposition.)
There is also an important class of problems, called NP-complete problems, with the property that if any of these problems can be solved by a polynomial worst-case time algorithm, then all problems in the class NP can be solved by polynomial worst-case time algorithms.
The satisfiability problem, is also an example of an NP-complete problem. It is an NP problem and if a polynomial time algorithm for solving it were known, there would be polynomial time algorithms for all problems known to be in this class of problems (and there are many important problems in this class). This last statement follows from the fact that every problem in NP can be reduced in polynomial time to the satisfiability problem. Although more than 3000 NP complete problems are now known, the satisfiability problem was the first problem shown to be NP-complete. The theorem that asserts this is known as the Cook-Levin theorem after Stephen Cook and Leonid Levin, who independently proved it in the early 1970s.
The P versus NP problem asks whether NP, the class of problems for which it is possible to check solutions in polynomial time, equals P, the class of tractable problems. If P=NP, there would be some problems that cannot be solved in polynomial time, but whose solutions could be verified in polynomial time. The concept of NP-completeness is helpful in research aimed
at solving the P versus NP problem, because NP-complete problems are the problems in NP considered most likely not to be in P, as every problem in NP can be reduced to an NP-complete problem in polynomial time. A large majority of theoretical computer scientists believe that P=NP, which would mean that no NP-complete problem can be solved in polynomial time.
One reason for this belief is that despite extensive research, no one has succeeded in showing that P = NP. In particular, no one has been able to find an algorithm with worst-case polynomial time complexity that solves any NP-complete problem. The P versus NP problem is one of the most famous unsolved problems in the mathematical sciences (which include theoretical computer science). It is one of the seven famous Millennium Prize Problems, of which six remain unsolved.
A prize of $1,000,000 is offered by the Clay Mathematics Institute for its solution.

所有能用多項式時間算法計算得到結(jié)果的問題宿礁，稱為多項式問題茬贵，也就是P湾揽，所有絕對不可能用多項式時間求解的問題晓猛，稱為指數(shù)型問題德绿。

有這樣一類問題忱叭，假使你得到了問題的解碉考，我要驗證你的解是否正確，驗證所花的時間是多項式袒哥，至于求解本身所花的時間是否是多項式我不管缩筛，可能有多項式算法，可能沒有堡称，也可能是不知道瞎抛，這類問題稱為NP問題。

NP概念的奧妙在于却紧，它躲開了求解到底需要多少時間這樣的問題桐臊，而僅僅只是強調(diào)驗證需要多少時間，從而為P與NP這一千年難題的產(chǎn)生埋下了伏筆晓殊。顯然断凶，P肯定是NP，因為你既然能用多項式求解巫俺，就肯定能用多項式驗證（大不了我再算一遍Ｈ纤浮），但NP是否是P誰也確定不了介汹。另外却嗡，目前已經(jīng)很明確的指數(shù)型問題也肯定不是NP。