A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard
(any NP-problem can be translated into this problem).
Examples of NP-hard problems include the Hamiltonian
cycle and traveling salesman problems.
In a landmark paper, Karp (1972) showed that 21 intractable combinatorial computational problems are all NP-complete.
See also
Graph Isomorphism Complete,
Hamiltonian Cycle,
NP-Hard
Problem,
NP-Problem,
P-Problem,
P Versus NP Problem,
Traveling
Salesman Problem
Explore with Wolfram|Alpha
References
Buckley, F. and Harary, F. Distance in Graphs. Redwood City, CA: Addison-Wesley, 1990.Garey, M. R.
and Johnson, D. S. Computers
and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H.
Freeman, 1983.Karp, R. M. "Reducibility Among Combinatorial
Problems." In Complexity
of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown
Heights, N.Y., 1972 (Ed. R. E. Miller and J. W. Thatcher).
New York: Plenum, pp. 85-103, 1972.Levin, L. A. "Universal
Searching Problems." Prob. Info. Transm. 9, 265-266, 1973.Papadimitriou,
C. H. and Steiglitz, K. Combinatorial
Optimization: Algorithms and Complexity. New York: Dover, 1998.Referenced
on Wolfram|Alpha
NP-Complete Problem
Cite this as:
Weisstein, Eric W. "NP-Complete Problem."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NP-CompleteProblem.html
Subject classifications
