411 REFERENCE · Wiktionary
NP-hard
Reference material by Wiktionary contributors. This retains its source identity and is not 411 news reporting.
English
Adjective
-
en 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.
en computing theory An alternative definition restricts NP-hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction.
Related terms
en NP-complete
en NP-easy
en NP-equivalent
Translations
hard
Finnish: fi NP-kova, fi NP-vaikea
French: fr NP-dur
Hebrew: he NP-קשה