Using Polynomial-Time Reduction to Prove Hardness

Question

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!

Answer 1

I'm not sure I follow what you mean with: `takes a problem A and breaks it down into many instances of problem $B$'. To be precise a many to one reduction from $A$ to $B$, converts instances of problem $A$ into instances of problem $B$.

When talking about time or space, one wants to convert instances from one problem to another in a certain time bound, this loosely said, to stay within a certain complexity class. Hence sometimes log space reductions are useful instead of polynomial time reductions.

Hardness is a term related to a certain class of problems. Intuitively it says: if one problem is hard for a certain class of problems it is at least as hard as any other problem in that class. Hence reductions only say something in one direction. i.e. if you have a reduction from $A$ to $B$, then you can only say that $A$ is just as hard as $B$, not the other way around!

Turing reductions are in essence slightly different, it says something about the hardness of $A$ having access to an oracle to $B$. This is particularly interesting when $A$ en $B$ are undecidable problems. If you want more on this I'll be more than happy to write more about this later, but I don't have more time now.