From what I understand of polynomial-time reduction, there are two instances of it: many-one and Turing.
Many-one simply breaks down problem A into many instances of problem B, and uses the (known) computational difficulty of B to evaluate A. They remind me almost of a divide-and-conquer approach... take a hard problem and keep breaking it down until you have workable units, then, decide whether the amount of those small units used to solve the big problem approaches infinity or not.
I'm not entirely sure that I fully understand Turing reduction, but here goes: Turing reductions reduce (break down?) problem A into problem B: that is to say, an algorithm that could solve problem A has a subroutine that solves problem B. In this way, an algorithm could be developed that solves A in which the call to problem B is replaced with the algorithm that solves problem B. This holds if A is B-recursive, B-computable, B-recursively enumerable, and B-computably enumerable.
(If I said anything silly or wrong, please let me know!)
Now, the problem I'm running into is how to apply these time-reductions to proving the hardness of a problem. The way I'm looking at it, for both cases, if A is reducible to B, then A is hard if B is hard. But if B is easy,how does one judge A?
For the Many-One reduction, I think that A can be called hard if A) the number of reductions it needs to make before a suitably solvable unit is reached approaches infinity, or B) the number of B's that A reduces to approaches infinity.
For a Turing reduction, I'm really having trouble drawing a logical line between the reduction and proof of hardness.
Does anyone have any insight on this idea?
Thank you very much!