# NP-hardness

## Complexity class / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about NP-hard?

Summarize this article for a 10 year old

In computational complexity theory, a computational problem *H* is called **NP-hard** if, for every problem *L* which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from *L* to *H*. That is, assuming a solution for *H* takes 1 unit time, *H*'s solution can be used to solve *L* in polynomial time.^{[1]}^{[2]} As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists.^{[3]} It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven.^{[4]} A simple example of an NP-hard problem is the subset sum problem.

Informally, if *H* is NP-hard, then it is at least as difficult to solve as the problems in NP. However, the opposite direction is not true: some problems are undecidable, and therefore even more difficult to solve than all problems in NP, but they are provably not NP-hard (unless P=NP).^{[5]}