A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic
Turing machine.
A P-problem (whose solution time is bounded by a polynomial) is always also NP. If a problem is known to be NP, and a solution to the problem
is somehow known, then demonstrating the correctness of the solution can always be
reduced to a single P (polynomial time) verification.
If P and NP are not equivalent, then the solution of NP-problems requires
(in the worst case) an exhaustive search.
Linear programming, long known to be NP and thought not to be P, was shown to be P by L. Khachian
in 1979. It is an important unsolved problem
to determine if all apparently NP problems are actually P.
A problem is said to be NP-hard if an algorithm for solving it can be translated into one for solving any other NP-problem. It is
much easier to show that a problem is NP than to show that it is NP-hard.
A problem which is both NP and NP-hard is called
an NP-complete problem.
