# 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-hardness?

Summarize this article for a 10 years old

In computational complexity theory, **NP-hardness** (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

A more precise specification is: a problem *H* is NP-hard when every problem *L* in NP can be reduced in polynomial time 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 any NP-hard problem would give polynomial time algorithms for all the problems in 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] Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.[5]