TOPICS
Search

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


See also

Complexity Theory, Exhaustive Search, Nondeterministic Turing Machine, NP-Complete Problem, NP-Hard Problem, P-Problem, P Versus NP Problem, Turing Machine

Explore with Wolfram|Alpha

References

Borwein, J. M. and Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.Clay Mathematics Institute. "P vs. NP." http://www.claymath.org/millennium/P_vs_NP/.Cook, S. "The P versus NP Problem." http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf.Crescenzi, P. and Kann, V. (Eds.). "A Compendium of NP Optimization Problems." http://www.nada.kth.se/~viggo/wwwcompendium/wwwcompendium.html.Greenlaw, R.; Hoover, H. J.; and Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford, England: Oxford University Press, 1995.Smale, S. "Mathematical Problems for the Next Century." Math. Intelligencer 20, No. 2, 7-15, 1998.Smale, S. "Mathematical Problems for the Next Century." In Mathematics: Frontiers and Perspectives 2000 (Ed. V. Arnold, M. Atiyah, P. Lax, and B. Mazur). Providence, RI: Amer. Math. Soc., 2000.

Referenced on Wolfram|Alpha

NP-Problem

Cite this as:

Weisstein, Eric W. "NP-Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NP-Problem.html

Subject classifications