# 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$. Jul 11, 2020 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? Jul 13, 2020 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. Jul 13, 2020 at 2:27
• I Got it. Thanks Jul 13, 2020 at 14:00

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.