NP-Complete Problem

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


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.

Subject classifications