Concept
NP-hardness
Overview
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. 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, but unproven, that P≠NP, it is unlikely that any polynomial-time algorithms for NP-hard problems exist.
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 probably not NP-hard (unless P=NP).
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
(2) _Non-inductiveness._--The second property by which infinite numbers are distinguished from finite numbers is the property of non-inductiveness. This will be best explained by defining the positive property of inductiveness which characterises the finite numbers, and which is named after the method of proof known as "mathematical induction." Let us first consider what is meant by calling a property "hereditary"…
Bertrand Russell, Our Knowledge of the External World as a Field for Scientific Method in Philosophy
States what NP-hardness is.
Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…
John Stuart Mill, A System of Logic, Ratiocinative and Inductive
States what NP-hardness is.
In respect to any complex eternal object, _S(D1, D2, ... Dn)_, the eternal objects _D1, ... Dn_, whose individual essences are constitutive of the individual essence of _S(D1, ... Dn)_, are called the components of _S(D1, ... Dn)_. It is obvious that the grade of complexity to be ascribed to _S(D1, ... Dn)_ is to be taken as one above the highest grade of complexity to be found among its components.
Alfred North Whitehead, Science and the modern world
States what NP-hardness is.
Related ideas
- Truth value
- Cryptography
- Turing machine
- Computational complexity theory
- Decision problem
- P versus NP problem
Place in the tradition
Part of Reductionism.