3
$\begingroup$

The definition of NP-hard problem in Wikipedia is : NP-hardness (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

There are NP-hard problems not in NP class. My question (more curiosity) concerns the NP in the definition. Since a NP-hard maybe is not in NP class, why we call it NP-hard?

When we say we have a NP-complete problem, then this problem is indeed in NP class.

$\endgroup$
  • $\begingroup$ Might help: stackoverflow.com/questions/1857244/… $\endgroup$ – Laxmana Feb 5 '17 at 14:50
  • 2
    $\begingroup$ It's just terminology. Maybe it's not optimal, but it's become customary. A problem is NP-hard if it's at least as hard as any problem in NP. $\endgroup$ – Yuval Filmus Feb 5 '17 at 15:09
  • 1
    $\begingroup$ Yes. I thought also that. There is not any deeper explanation. $\endgroup$ – 111 Feb 5 '17 at 15:17
  • $\begingroup$ Maybe because it could be in NP? $\endgroup$ – Ribz Feb 5 '17 at 17:05
1
$\begingroup$

Here is a definition which describes the relationship between hard and complete:

Given a set C of problems and a reduction R, it is natural to ask if there are problems Π ∈ C such that any problem Π′∈C, R-reduces to Π. Such “maximal” problems are called in complexity theory complete problems. Let C be a class of problems and R be a reduction. A problem Π ∈ C is said to be C-complete (under R-reduction) if for any Π ∈′ C, Π′ ≤R Π. A C-complete problem (under reduction R) is then (in the sens of this reduction) a computationally hardest problem for class C. For instance, in the case of NP-completeness, NP-complete problems (under Karp-reduction) are the hardest problems of NP since if one could polynomially solve just one of them, then one would be able to solve in polynomial time any other problem in NP. Let C be a class of problems and R a reduction. A problem Π is said to be C-hard (under R-reduction) if for any Π ∈′ C, R Π≤ Π ′. In other words, a problem Π is C-complete if and only if Π ∈ C and Π is C-hard.

References

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.