# Is there any decision problem not in NPH but can be reduced to a NPH problem?

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...

• Welcome to CS.SE. What does NPH stand for? What are your thoughts? What possible examples have you thought of? Have you tried working through a few examples where A/B are/aren't in NP? – D.W. Dec 15 '16 at 4:16
• NPH stands for NP-Hard. I don't have any possible examples but I know counter examples shouldn't be in NP otherwise counter example in NP implies P=/=NP. – jotae Dec 15 '16 at 5:50
• Sorry, 'counter examples shouldn't be in NP' is wrong. What I mean was, as P=NP is open, whether the counter examples exist in NP is also open. – jotae Dec 15 '16 at 5:56
• You don't need a counter-example to show that the logic is broken. – Raphael Dec 15 '16 at 6:20

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.

1. If P = NP, then NPH contains all (non-trivial decision) problems. Then, the statement is silly.
2. 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).

• I omitted the type of reduction by mistake. The reduction in the statement should be replaced with polynomial time reduction. Anyway, as you wrote, it is meaningless... maybe I misread NP as NPH at that time :'( ... Thank you for your answer. – jotae Dec 15 '16 at 6:59
• I don't think there's any mistake on the teacher's part. It's a true/false question that tests whether you know the definition of NP-hardness and basic properties of reductions. – David Richerby Dec 15 '16 at 8:21

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).

• Even if P=NP, $\emptyset$ and $\Sigma^*$ aren't NP-hard under many-one reductions. – David Richerby Dec 15 '16 at 20:04