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:
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).
If $a \in A$, is $f(a) \in B$?
If $a \notin A$, is $f(a) \notin B$? (alternatively, if $f(a) \in B$, is $a \in A$)?
Does $f$ take polynomial time?
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).
