Definitions
from Wiktionary, Creative Commons Attribution/Share-Alike License.
- adjective computing theory A problem H is NP-hard if and only if there is an
NP-complete problem L that is polynomial time Turing-reducible to H. - adjective computing theory An alternative definition restricts NP-hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction.
Etymologies
Sorry, no etymologies found.
Support
Help support Wordnik (and make this page ad-free) by adopting the word NP-hard.
Examples
-
Finding a global minimum is NP-hard, and bubbles don't help.
-
What has happened here is that, as computer science tries to understand ai it has realized that many aspects of ai are NP-complete or NP-hard, and a few aspects are not.
-
What has happened here is that, as computer science tries to understand ai it has realized that many aspects of ai are NP-complete or NP-hard, and a few aspects are not.
-
Consider the set of all practical instances of some NP-hard problem that one particular human being will be interested in solving in her lifetime.
Obsessively barking up the wrong tree - The Panda's Thumb 2007
-
In many practical applications one *needs* the solutions to NP-hard problems.
Obsessively barking up the wrong tree - The Panda's Thumb 2007
-
Paul, to compound my sins, I will just mention that the optimization version of the traveling salesman problem you describe find the shortest route… is actually NP-hard.
-
However, the computational space (available memory) and time complexity of these methods are so extreme as to dwarf those of the optimal algorithms for the ESSCP and MESCP (which were already NP-hard).
Conservation Biology Sarkar, Sahotra 2004
-
NP-hard problems in polynomial time depend on energy gap arguments.
Ars Technica Chris Lee 2011
-
NP-hard problem which is in practice unsolvable in a reasonable amount of time.
Site Home Eric Lippert 2011
-
Identifying the minimum number of rSPRs separating two trees is NP-hard, but the problem can be reduced to fixed parameter tractable.
BioMed Central - Latest articles Tobias Hill 2010
Comments
Log in or sign up to get involved in the conversation. It's quick and easy.