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$
4
  • $\begingroup$ Might help: stackoverflow.com/questions/1857244/… $\endgroup$
    – Laxmana
    Commented Feb 5, 2017 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$ Commented Feb 5, 2017 at 15:09
  • 1
    $\begingroup$ Yes. I thought also that. There is not any deeper explanation. $\endgroup$
    – 111
    Commented Feb 5, 2017 at 15:17
  • $\begingroup$ Maybe because it could be in NP? $\endgroup$
    – Ribz
    Commented Feb 5, 2017 at 17:05

1 Answer 1

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 and acknowledge you have read our privacy policy.

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