NP-Complete Problem

A problem which is both NP (solvable in nondeterministic Polynomial time) andNP-Hard (can be translated into any other NP-Problem). Examples of NP-hard problems includethe 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.

• Operator
• Optimization Theory
• Or
• Orbifold
• Orbison's Illusion
• Orbit (Group)
• Orbit (Map)
• Orchard-Planting Problem
• Orchard Visibility Problem
• Order (Algebraic Curve)
• Order (Algebraic Surface)
• Order (Conjugacy Class)
• Order (Difference Set)
• Ordered Geometry
• Ordered Pair
• Ordered Tree
• Order (Field)
• Order (Group)
• Ordering
• Ordering Axioms
• Order (Modulo)
• Order (Ordinary Differential Equation)
• Order (Permutation)
• Order (Polynomial)
• Order Statistic