Alternative Definitions
An alternative definition of NP-hard that is often used restricts NP-hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction. So, formally, a language L is NP-hard if ∀L' ∈ NP, L' ≤ L. If it is also the case that L is in NP, then L is called NP-complete. However, under this definition, the trivial decision problem (the one that accepts everything) and its complement would provably not be in NP-hard, even if P = NP, since no other problems can many-one reduce to these two problems.
Read more about this topic: NP-hard
Famous quotes containing the words alternative and/or definitions:
“Our mother gives us our earliest lessons in love—and its partner, hate. Our father—our “second other”Melaborates on them. Offering us an alternative to the mother-baby relationship . . . presenting a masculine model which can supplement and contrast with the feminine. And providing us with further and perhaps quite different meanings of lovable and loving and being loved.”
—Judith Viorst (20th century)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)