I just have taken an algorithm class exam and there was a T/F problem 'one can show that a problem A is in NPH by giving a polynomial reduction from A to a NPH problem B'. I know the direction of reduction is silly, but no counter examples come to mind right now...
Assuming you're using many-one reductions, $\emptyset$ and $\Sigma^*$ are not NP-hard (exercise: prove this!), but they can be reduced to any NP-hard problem. Therefore, the statement, "one can show that a problem $A$ is in NPH by giving a reduction from $A$ to a NPH problem $B$" is false.
This is the statement:
one can show that a problem A is in NPH by giving a reduction from A to a NPH problem B
There are two cases.
- If P = NP, then NPH contains all (non-trivial decision) problems. Then, the statement is silly.
- If P ≠ NP, then any problem in P serves as a counter-example; the statement is wrong.
Hence, the statement is not something we should make; I daresay it's wrong.
Please check that there was no silly mistake on your or your teacher's part. The statement is correct if you replace NPH with NP (and use a fitting type of reduction, which is assumed).
Saying problem B is NP-hard means precisely that any problem in NP has a polynomial reduction to B.
Consequently, giving a polynomial reduction from problem A to problem B wouldn't show anything useful (assuming A is in NP) -- we already knew there was one, because we knew B was NP-hard.
So the statement is not true unless all problems in NP are NP-hard (i.e. unless P=NP).