# If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

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?

• 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$. – Watercrystal Jul 11 '20 at 2:22
• 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? – FY Gamer Jul 13 '20 at 0:53
• Yes, this is how it goes. Note however that this may not work with other classes or reductions, but for this case it holds. – Watercrystal Jul 13 '20 at 2:27
• I Got it. Thanks – FY Gamer Jul 13 '20 at 14:00

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.