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?

Improve this question
$\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, 2020 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, 2020 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, 2020 at 2:27
  • $\begingroup$ I Got it. Thanks $\endgroup$
    – FY Gamer
    Jul 13, 2020 at 14:00

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.