> For the complete documentation index, see [llms.txt](https://alfredo-reyes-montero.gitbook.io/metaheuristics/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alfredo-reyes-montero.gitbook.io/metaheuristics/optimization/readme/introduction/np-hard-problems.md).

# NP-Hardness Problems

**NP-hardness** (non-deterministic polynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP". More precisely, 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, we can use H‎'s solution to solve L in polynomial time. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered difficult.

A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "**N**on-deterministic **P**olynomial acceptable problems". Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has not been proven. Moreover, the class P in which all problems can be solved in polynomial time, is contained in the NP class.