Is an NP-hard problem which is in NP is NP-complete?

Question

I'm reading Combinatorial Optimization book by Bernhard Korte and Jens Vygen. There's a part that they said:

It is an open question whether each $NP$-hard decision problem $A \in NP$ is $NP$-Complete, because of the difference between polynomial reduction and polynomial transformation.

I understand that, but when I read wikipedia article about NP-complete, I see this picture

According to wikipedia, a decision problem is $NP$-complete when it is both in $NP$ and $NP$-hard, which make me confused. Can someone help me understand the difference between the book and wikipedia?

Definition 15.15. Let P1 and P2 = (X, Y) be decision problems. Let f : X → {0, 1} with f (x) = 1 for x ∈ Y and f (x) = 0 for x ∈ X \ Y . We say that P1 polynomially reduces to P2 if there exists a polynomial-time oracle algorithm for P1 using f

Definition 15.17. Let P1 = (X1, Y1) and P2 = (X2, Y2) be decision problems. We say that P1 polynomially transforms to P2 if there is a function f : X1 → X2 computable in polynomial time such that f (x1) ∈ Y2 for all x1 ∈ Y1 and f (x1) ∈ X2 \ Y2 for all x1 ∈ X1 \ Y1.

Answer 1

Check the definitions of NP-completeness and NP-hardness. I suspect they use Karp reductions for one and Cook reductions for the other.

Then, the quote makes sense: it is indeed unknown if Cook reductions and Karp reductions are equivalent in this sense. This is related to the question whether co-NP = NP; Cook reductions can not separate the two but Karp reductions might. See here for some details.

However, the authors use different definitions than (most of) the rest of the CS world: the widely accepted standard is to use Karp reductions. I recommend you read our reference question (and get a better book).

---

To be fair, the authors want to talk about optimization problems, in which case they need a notion of (NP-)hardness that is not tied to decision problems. Karp reductions won't get them there directly.

They picked a poor way out, arguably, by defining the notions differently from everybody else. There are cleaner (but more involved) ways, defining complexity classes for optimization problems rigorously, providing them with their own types of reduction, and tying them to the classic decision-problem classes using threshold languages.

Answer 2

NP is an abbreviation of the term "non-deterministic polynomial". Informally, it means a problem belonging to the class NP can be 'solved' (formal term is 'decided') by using a non-deterministic Turing machine (TM) in the number of steps which are polynomial in the input size. Input size is usually no. of TM cells used by the input problem encoded in certain format. Intuitively, it is an amount of memory required to write input on TM tape.

You should note that NP is a complexity class of problems and not the problem instance itself. The complexity class is a set of problems which requires similar amount of resources (time and/or memory space) to solve.

Meaning of the term 'Hard': I think you have misunderstood meaning of the term 'hard'. Hardness is the measure for comparing amount of resources needed to solve problems in various complexity classes. For a problem in NP, time requirement is polynomial in input size. Problems in the class NP-hard need at least polynomial no. of steps, but they may actually need more. Informally speaking, all problems which have same or more resource requirement (hence at least that much hard to solve) than problems in NP are NP-hard.