Difference between NP-hard and NP-complete I am struggling to tell the difference between the definitions of NP-hard and NP-complete problems. I know that NP-complete problems are NP-hard, so this tells me that $$\text{$P_1$ polynomially transforms to $P_2$}\quad\Rightarrow\quad\text{$P_1$ polynomially reduces to $P_2$},$$
but seeing why this is true is not obvious from the definitions.
These were the definitions given:

Let $P_1=(X_1,Y_1)$ and $P_2=(X_2,Y_2)$ be two decision problems—i.e. $X_i$ is a set of all instances and $Y_i$ is the set of "yes instances". Let $g\colon X_2\to \{0,1\}$ be such that $g(x)=1$ if and only if $x\in Y_2$.

*

*We say that $P_1$ polynomially reduces to $P_2$ if there exists a polynomial time oracle algorithm for $P_1$ using $g$.

*We say that $P_1$ polynomially transforms to $P_2$ if there exists a function $f\colon X_1\to X_2$ computable in polynomial time such that $f(x_1)\in Y_2$ for all $x_1\in Y_1$ and $f(x_1)\in X_2-Y_2$ for all $x_1\in X_1-Y_1$.

Then, a problem is

*

*NP-hard if all problems in NP polynomially reduce to it; and

*NP-complete if all problems in NP polynomially transform to it.


What is the difference between polynomial reduction and polynomial transformation? I am unsure what the definition of polynomial reduction means exactly; I had thought the "polynomial time oracle algorithm" would be defined in the same way that $f$ was.
 A: Their "polynomially reduces" means polynomially Turing-reduces, and

their "polynomially transforms" ​ means polynomially many-one reduces.

In standard terminology, which I'll use for this answer,

reduce/reduces/reduction/reductions by default 
refer to many-one.
"using $g$" ​ / ​ "Turing reduction" ​ ​ ​ mean the same thing, and are defined via oracle machines.

Many-one reductions are equivalent to the special case in which [[the machine always queries

the oracle exactly once] and [the machine always gives the same output as the oracle]].

To compute $\hspace{.04 in}f\hspace{-0.03 in}$, replace "enter the ask state" with "output the contents of the oracle tape".
Now, for $\;\;\;$ many-one reduction $\: \implies \:$ Turing reduction $\;\;\;$:

You have an oracle for $g$ and can evaluate $\hspace{.03 in}f\hspace{-0.03 in}$, so just output $g(\hspace{.05 in}f(x))$. $\:$ It's that simple.
Their definition of NP-hard is correct;

different notions of reduction yield different definitions of NP-hard.

Their definition of NP-complete is missing an important part:

L is NP-complete $\;\; \iff \;\;$ L is NP-hard ​ and ​ L is in NP $\;\;\;\;\;$ .
