<complexity> A set or property of computational search problems.

A problem is NP-hard if solving it in polynomial time would make it possible to solve all problems in class NP in polynomial time.

Some NP-hard problems are also in NP (these are called "NP-complete"), some are not.

If you could reduce an NP problem to an NP-hard problem and then solve it in polynomial time, you could solve all NP problems.

See also computational complexity.

[Examples?]

< Previous Terms |
Terms Containing NP-hard |
Next Terms > |

no-write allocation NP np NPC NP-complete |
brute force DNA computing knapsack problem metaheuristic NP-complete |
NPL NPPL N-Prolog NP time NQS |

WeWork Office Space & Coworking

Address: 115 Broadway, New York, NY 10006

Hours: Opens 9AM - 6PM

Phone: +1 646-396-3519

shape

shape