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.
所有能用多项式时间算法计算得到结果的问题，称为多项式问题，也就是P，所有绝对不可能用多项式时间求解的问题，称为指数型问题。
有这样一类问题，假使你得到了问题的解，我要验证你的解是否正确，验证所花的时间是多项式，至于求解本身所花的时间是否是多项式我不管，可能有多项式算法，可能没有，也可能是不知道，这类问题称为NP问题。
NP概念的奥妙在于，它躲开了求解到底需要多少时间这样的问题，而仅仅只是强调验证需要多少时间，从而为P与NP这一千年难题的产生埋下了伏笔。显然，P肯定是NP，因为你既然能用多项式求解，就肯定能用多项式验证（大不了我再算一遍！），但NP是否是P谁也确定不了。另外，目前已经很明确的指数型问题也肯定不是NP。
