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