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


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