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