NP-Problem

A problem is assigned to the NP (nondeterministic Polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing Machine. (A nondeterministic Turing Machine is a ``parallel'' Turing Machine which can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate.) A P-Problem (whose solution time is bounded by a polynomial) is always also NP. If a solution to an NP problem is known, it can be reduced to a single P (Polynomial time) verification.

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 not known 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 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.

References

Borwein, J. M. and Borwein, P. B. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.

Greenlaw, R.; Hoover, H. J.; and Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford, England: Oxford University Press, 1995.