info prev up next book cdrom email home

NP-Complete Problem

A problem which is both NP (solvable in nondeterministic Polynomial time) and NP-Hard (can be translated into any other NP-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 Hamiltonian Cycle, NP-Hard Problem, NP-Problem, P-Problem, Traveling Salesman Problem


References

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). New York: Plenum, pp. 85-103, 1972.




© 1996-9 Eric W. Weisstein
1999-05-25