dictionary· e01.org

dictionary · English Wiktionary

np-hard

Pronunciation N P2 definition(s) across 1 part(s) of speech · fetched 2026-11-19

  • Source Wiktionary
  • Retrieved 2026-11-19
  • Licence CC BY-SA 4.0 (Wiktionary dump)
  • Cache cache
  • Language English

np-hard is an English headword with 2 Wiktionary senses (Adjective).

Adjective2 senses
  1. 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.

  2. An alternative definition restricts NP-hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction.

Source
English Wiktionary
Record
np-hard
Retrieved
2026-11-19
Licence
CC BY-SA 4.0 (Wiktionary dump)
Completeness
Cached copy of the source entry; not a rewrite or a generated definition.