cover image

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

SHOW ALL QUESTIONS

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.

Euler diagram for P, NP, NP-complete, and NP-hard set of problems.
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)

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]