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.

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

1999-05-25