0
$\begingroup$

I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-complete, can I say that A is NP-complete too?

Actually, I would say yes, because if I can convert a problem that I don't know how to solve to one that I know, then that problem must be at least as hard as the reducible one. So, A should be NPC.

However, I got to another idea that I can convert an easier problem to a hard one, so I could say that A is NP, but I couldn't guarantee that it's NPC.

Which ideia is correct?

$\endgroup$
4
  • 1
    $\begingroup$ There is already an answer to the question, but when grading things or giving tutorials, I found that a lot of people have problems with this. I like to explain it this way: We write $A \leq_\mathsf{P} B$ if we can poly-time reduce $A$ to $B$, which is good notation! It basically can be read as the "hardness" of $A$ being lower or equal to the one of $B$. Now, $\mathsf{NP}$-hardness is a lower bound on hardness, so to prove that some problem $A$ is $\mathsf{NP}$-hard you need to establish a suitable lower bound on its hardness, i.e. show that $B\leq_\mathsf{P} A$ for an $\mathsf{NP}$-hard $B$. $\endgroup$ – Watercrystal Jul 11 '20 at 2:22
  • $\begingroup$ So I could say that i the case that $A \leq_\mathsf{P} B$ and $B$ is NP-complete, I can say that $A$ is NP, because it's "hardness" should be lower or equal to $B$'s "hardness". But if I had $A \leq_\mathsf{P} B$ and $A$ is NP-complete, then $B$ is NP-hard. Did I get this right? $\endgroup$ – FY Gamer Jul 13 '20 at 0:53
  • $\begingroup$ Yes, this is how it goes. Note however that this may not work with other classes or reductions, but for this case it holds. $\endgroup$ – Watercrystal Jul 13 '20 at 2:27
  • $\begingroup$ I Got it. Thanks $\endgroup$ – FY Gamer Jul 13 '20 at 14:00
2
$\begingroup$

You can indeed not guarantee that A is NP-complete.

Problem A: Given is a single number X ≥ 1. Is X equal to 1? Clearly in P, and in NP, but of course not NP-complete.

Problem B: Given n items of size $s_i$ ≥ 1, a bin size B ≥ 1, and an integer k ≥ 1, can the n items be put into k bins of size B? This one is NP complete.

A can be reduced to B in polynomial time: Just take 1 item of size X, let B = 1 and k = 1.

$\endgroup$

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.