4
$\begingroup$

This is a question on a practice final.

Problem A is polynomially reducible to problem B. Which of the following statements is correct?

I. If problem A is solvable in a polynomial time then problem B is solvable in polynomial time.

II. If problem A is NP-complete then problem B is NP-complete.

III. If problem A is NP-hard then problem B is NP-hard

a) I

b) II

c) III

d) I and II

e) I, II and III

We are told that the solution is (c), but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A. (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)


This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

$\endgroup$
12
$\begingroup$

Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not accurate).

It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I don't have to type it over and over); a reduction (from A to B) is just an algorithm that turns an instance of A into an instance of B, with the special property that if we know/can figure out/can use magic to find out the answer to the instance of B, we know the answer to the original instance of A. This gives us a way of solving problem A if we already know how to solve B.

This is why we say things like "B is at least as hard as A", because any algorithm for B immediately gives an algorithm for A. To flip it around, if we knew B was "easy", then A must also be "easy" (for some notion of "easy").

Notice that this relationship is not symmetric - knowing how to solve A doesn't tell us anything about how to solve B (given that all we have is the single reduction). If we had more information, maybe it would, maybe it wouldn't, but from the reduction alone we get nothing in that direction.

So then for I., we know we can turn an A into a B, and that we can solve an A, but this tells us nothing about B.

For III., we already know that A is hard (NP-hard!), and the reduction tells us that B is at least as hard as A, so B must also be NP-hard. The formal truth behind this intuition comes from the definition of NP-hardness. Remember that A being NP-hard means every single problem in NP has a reduction to A. We also know that A reduces to B, so how does this show B is NP-hard? We can compose the reductions. For every C in NP, we can reduce every instance of it to an instance of A, then take that instance of A and use our new reduction to turn it into an instance of B (as an exercise you might want to think about why we still know this is all polynomial time etc.). So this gives us a way of turning every problem C in NP into problem B, which is the definition of NP-hardness.

Coming back to II., this one again relies on definitions. NP-completeness is NP-hardness, plus the additional property that the problem is in NP. So saying problem A is NP-complete means problem A is NP-hard and A is in NP. We've just seen that the reduction to B tells us that B is NP-hard, so we have that part, but just like part I., where A being in P didn't tell us whether B was in P or not, A being in NP doesn't tell us whether B is in NP or not. It might be, but the reduction doesn't give us this information.

$\endgroup$
0
$\begingroup$

If Problem A is polynomially reducible to problem B then B is at least as hard as A. So only (III) is true. For NPC, NP property is needed so (II) is not true.

$\endgroup$
  • 2
    $\begingroup$ I feel that this answer would be better if you added some explanation about the last sentence -- anyone who knows the answer can figure out what you mean but your audience is people who don't know. $\endgroup$ – David Richerby Jul 4 '18 at 13:08

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.