1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Dec 15 '16 at 4:16
  • $\begingroup$ 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. $\endgroup$ – jotae Dec 15 '16 at 5:50
  • $\begingroup$ 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. $\endgroup$ – jotae Dec 15 '16 at 5:56
  • $\begingroup$ You don't need a counter-example to show that the logic is broken. $\endgroup$ – Raphael Dec 15 '16 at 6:20
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jotae Dec 15 '16 at 6:59
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 15 '16 at 8:21
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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