1
$\begingroup$

I'm so bad at solving the problem of the type:

"If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..."

That I have to come here and ask these silly questions each and every time I encounter them.

Is there a good way of using the Venn Diagram shown below to tackle these kind of problem? enter image description here

For example, how can I prove that If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ can be NP-hard using the above diagram?

If not possible, what would be another way to drill this into my head?

$\endgroup$
2
  • $\begingroup$ I always find the definitions helpful. "B is reducible to A" writes $B \leq_p A$ which already suggests "B is easier than A" (up to polynomial factors) -- start from there. $\endgroup$ – Raphael Dec 16 '14 at 8:12
  • $\begingroup$ @Raphael This is good to know. So let the difficulty hierarchy is like: P < NP < NP Hard < NP Complete? If that is the case this can be a good way to know if one thing is reducible to another...But my other question is whether one problem is ALWAYS reducible to another in the same complexity class, do you have an answer to that? $\endgroup$ – Olórin Dec 16 '14 at 22:38
1
$\begingroup$

As Raphael said the definitions are important, especially if you try to create proofs. These definitions are not always captured in the Venn diagram.

The definition of NP-complete is not made clear from the diagram and will not help you to reason about

"If A is an NP-complete problem, $B$ is reducible to $A$, then $B$ is...".

You cannot see from the diagram that this must mean that $B$ is NP.

To answer your question if it is not possible how you will be able to drill it into your head is much more complicated. But again the first step needs to be the definitions.

If you know that NP-completeness implies two properties of $A$ by definition, then you can take the next step.

What does $B$ reducible to $A$ means when regarding these two properties. Do the properties of $A$ tell anything about $B$?

The second property says that any problem in NP reduces to $A$ in polynomial time. So if $B$ reduce to $A$ in polynomial time then $B$ is in NP.

$\endgroup$
1
  • $\begingroup$ Your last sentence is true but misleading. The fact that everything in NP reduces to A does not immediately mean that everything that reduces to A is in NP. Actually, everything that reduces to A is in NP but that's a theorem, not an immediate consequence of the definition. The proof of the theorem is that composing the reduction with the algorithm for A gives you a nondeterministic polytime algorithm for B, and that's what tells you that B is in NP. $\endgroup$ – David Richerby Dec 16 '14 at 11:57
1
$\begingroup$

The Venn diagram doesn't help very much.

Let's take your example of "If A is an NP complete problem, B is reducible to A, then B is..." NP-completeness tells you that everything in NP is reducible to A but that's not the question you're trying to solve. The question you're trying to solve is the converse: whether everything reducible to A is in NP. (It happens that it is but that's a theorem, not something that you can see immediately from the definitions.)

To use an analogy, your Venn diagram tells you that every elephant has four legs but you're trying to determine whether everything that has four legs is an elephant.

$\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.