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

Comments

Log in or sign up to get involved in the conversation. It's quick and easy.