An NP-problem is a decision problem in the class NP (nondeterministic polynomial time), meaning that it is solvable in polynomial
time by a nondeterministic Turing
machine. Equivalently, a deterministic Turing machine
running in polynomial time accepts some certificate
of length polynomial in the input size iff the input is a
yes-instance.
Every P-problem is also in NP. If P and NP are distinct, some NP-problems have no polynomial time algorithm.
This does not imply that exhaustive search is
necessary. The P versus NP problem asks whether
every NP-problem is a P-problem.
For example, deciding feasibility of a system of linear inequalities with rational coefficients is
a P-problem, as shown by Khachiyan (1979) in his work
on linear programming.
A decision problem is NP-hard if every NP-problem can be reduced to it by a polynomial
time transformation that preserves yes- and no-instances. A decision
problem that is both in NP and NP-hard is
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."
https://www.claymath.org/millennium/p-vs-np/.Cook,
S. "The P versus NP Problem." https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf.Crescenzi,
P. and Kann, V. (Eds.). "A Compendium of NP Optimization Problems." https://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.Khachiyan, L. G. "A Polynomial Algorithm in Linear
Programming." Dokl. Akad. Nauk SSSR 244, 1093-1096, 1979. https://www.mathnet.ru/eng/dan42319.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 Resource. https://mathworld.wolfram.com/NP-Problem.html
Subject classifications
