0
$\begingroup$

Let's say you want to show $A \leq_{p} B$ (this is usually in the context of showing $B$ is NP-complete, but I'm just asking about the reductions. We are specifically looking at polynomial (Karp) reductions. Also, specifically decision problems--the answer is YES or NO) Here's how I'm thinking of it. Reach into a bag for a hypothesis function f. Now check:

  1. Does $f$ actually map instances of $A$ to instances of $B$? (eg, if I am reducing to Traveling Salesman, did I actually make a complete graph).

  2. If $a \in A$, is $f(a) \in B$?

  3. If $a \notin A$, is $f(a) \notin B$? (alternatively, if $f(a) \in B$, is $a \in A$)?

  4. Does $f$ take polynomial time?

  5. Given a certificate to $a \in A$, will I be able to concoct a certificate for $f(a) \in B$?

Sometimes, these restrictions will yield more questions. If $f$ didn't work, then I try to consider why it didn't work and how I can change $f$ so that it works. But I'm often getting stuck by not being able to think of all the possibilities for $f$. If $f$ works on all these things, you can conclude $A \leq_{p} B$. (5 may not be necessary, I'm not sure. But it's still a good question to ask). These questions come about from using the definition of what a polynomial reduction is. But I was wondering, are there other questions or strategies that can be applied in general? I think (in the context of an exam) I will be told what to reduce from (things like Subset-sum, Hamiltonian paths, Traveling Salesman, etc).

$\endgroup$
3
  • 1
    $\begingroup$ At least try to make in "informed reach" into the bag: sure you can always reduce from e.g. 3-SAT, but it might be much easier to reduce from a problem that is already close. Also, see our reference question. $\endgroup$
    – Juho
    Feb 16, 2015 at 20:34
  • $\begingroup$ This question is well put, but it is a duplicate. The reference question needs entries for some "templates", though. $\endgroup$
    – Raphael
    Feb 17, 2015 at 7:32
  • $\begingroup$ This question is in context of already having been told (or decided yourself) what $A$ and $B$ are. So when I say reach into the bag, it means I find functions that would map $A$ to $B$. The reference question seems to talk about how to figure out what $A$ is. Not sure if that makes my question different or not (though ref question was helpful). $\endgroup$ Feb 26, 2015 at 21:50

0

Browse other questions tagged or ask your own question.