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

3 Answers 3

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$
2
  • $\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
    Commented Dec 15, 2016 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$ Commented Dec 15, 2016 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$
1
  • $\begingroup$ Even if P=NP, $\emptyset$ and $\Sigma^*$ aren't NP-hard under many-one reductions. $\endgroup$ Commented Dec 15, 2016 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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