7
$\begingroup$

I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($HALT_{TM}$)is undecidable. I know we can assume that it is decidable and then try to build a decider for the acceptance problem, which is impossible. But though we are using the Acceptance Problem ($A_{TM}$) to help solve the decidability of the Halting Problem, we have reduced the Acceptance Problem to the Halting Problem, not the other way around, right?

I sometimes get a little bit confused when I encounter questions that ask me to deploy a reduction; I will be asked to reduce language $x$ to $y$, but what that means is that $y$ is a simpler instance of a problem of $x$, right (or at least should be)? I'm assuming it's impossible to reduce a simpler version of a problem to a more complex version of a problem, am I right in believing that?

$\endgroup$
  • $\begingroup$ If we believe that it's hard to build a ladder to the moon, then we must also believe that it's at least as hard to build a device that duplicates any object -- since if such a device was easy to build, then we could put a regular ladder in it, attach the resulting two ladders together to produce a double-height ladder, and then repeat this process a few times, and thus easily solve the problem we assumed to be hard. Here I've reduced the problem of building a moon-ladder to the problem of building an object duplicator to show that the latter is at least as hard as the former. $\endgroup$ – j_random_hacker Nov 14 '17 at 14:38
  • $\begingroup$ @j_random_hacker That analogy seems rather convoluted and it quickly seems to break down. I could just use a regular ladder factory to get my ladders (so a duplicator is not necessary) and, after I've stuck a few ladders together, the whole construction will be so flimsy that it will collapse under its own weight (so a duplicator is not sufficient). $\endgroup$ – David Richerby Nov 14 '17 at 15:57
  • 3
    $\begingroup$ @DavidRicherby: Granted the structural considerations are a big problem, no argument there :) Ignoring those, though, the fact that a ladder factory suffices is not an issue: to show problem A is at least as hard as problem B it's enough to show all instances of B can be solved by transforming to instances of A, and thus solving A solves B too; the existence of other solutions for B is irrelevant. (Indeed the fact an object duplicator can be used to implement a ladder factory means the "duplicator" problem is at least as hard as the "ladder factory" problem, which seems a valid conclusion!) $\endgroup$ – psmears Nov 14 '17 at 16:31
  • 4
    $\begingroup$ Possible duplicate of When problem A reduces to problem B, which problem is more complex? $\endgroup$ – Kevin - Reinstate Monica Nov 14 '17 at 16:33
  • 3
    $\begingroup$ @DavidRicherby: By writing "to the moon", I guess I drew attention to the flimsiest part of the analogy (namely, the flimsiness of the ladders). And without room to define "hard", I wanted a technique needing "a linear amount of work" or worse (like your ladder factory) to qualify as "hard", and "a logarithmic amount of work" (like my duplicator) to qualify as "easy". Perhaps this analogy doesn't work, but I think some kind of somewhat accurate, somewhat realistic analogy should be possible and helpful. $\endgroup$ – j_random_hacker Nov 14 '17 at 17:50
17
$\begingroup$

Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing $A$ to $B$ or $B$ to $A$?" moment.

Reducing $A$ to $B$ produces a statement of the form "If I could solve $B$, then I'd also know how to solve $A$". "Solve" in this sense could mean "compute using any Turing machine", or "compute in polynomial time" or whatever other notion of solution your context requires.

This may seem counterintuitive, since "$A$ reduces to $B$" implies that solving $B$ is at least as hard as solving $A$, so you haven't reduced the difficulty. However, you can think of it as reducing the number of problems you need to solve. Imagine that, at the start of the day, your goals were to find an algorithm for $A$ and an algorithm for $B$. Well, now that you've found a reduction from $A$ to $B$, you've reduced your goals to just finding an algorithm for $B$.

$\endgroup$
  • 2
    $\begingroup$ ""If I could solve B, then I'd also know how to solve A"" - Also, if you know solving A is hard, then you also know solving B is at least as hard. $\endgroup$ – G. Bach Nov 14 '17 at 18:16
  • 2
    $\begingroup$ A physicist and a mathematician were each asked to remove two nails, one of them punched all the way into the wall, the other just halfway. The physicist first pulled out the one that was halfway in and then, after toiling some time, managed to pull out the second one. The mathematician started with the one that was all the way in the wall, since it was more interesting. After some considerable time and effort, he managed to get it out. Then he looked at the other one, and uttering the words, "This can be simplified to an already solved case," he punched it all the way into the wall. $\endgroup$ – Wildcard Nov 15 '17 at 2:44
5
$\begingroup$

No. When $A$ reduces to $B$, it intuitively means that $A$ is simpler than $B$, not the other way around.

More practically: assume you want to check $x \in A$. Instead of doing that in some way, you transform $x$ according to some (reduction) function $y=f(x)$. You now have to check $y \in B$.

You haven't yet solved the initial problem $x \in A$, since now you are left with another problem to solve: $y \in B$. This means that you have reduced the initial problem to another one.

It might seem counter-intuitive at first that we reduce easy things to more complex ones. Indeed, pragmatically, why should one wanting to solve an easy task reducing themselves to an harder task? Wouldn't we like to reduce our task to an even easier task, instead?

However, the truth is: if we could solve a hard task $A$ reducing it to an easy task $B$, this means that $A$ was not really harder than $B$. Indeed, if solving $A$ can be achieved by applying the reduction function, and then solving the "easier" $B$, it means that $A$ was easier than $B$ in the first place.

$\endgroup$
5
$\begingroup$

A reduction from $A$ to $B$ is something that does part of the work needed to do $A$ and what remains to do is $B$. For example, "getting food" can be reduced to "cooking" by "getting ingredients". This means that "cooking" is harder than "getting food": Anyone that can "cook" can "get food" (assuming that the reduction "getting ingredients" always works, for example in the presence of a place giving ingredients for free).

Drawing things tend to make them easier to understand:

enter image description here

You want to build the blue box (which represents an algorithm that takes an input $x$ and decides if $x\in A$). The reduction is then the red box, and once you have it, the only thing that remains to do in order to build the blue box is building the green box. So if you have a red box (that reduces $A$ to $B$), building the green box (that decides $B$) is at least as hard as building the blue one (that decides $A$): If you have a green box it is very easy to build a blue one, while if you build a blue box you may not be able to build a green box.

Note that the reasons for the two conditions defining a reduction appear on this drawing: the fact that $f$ is computable means that you can build the red box, while the fact that $f(x)\in B\iff x \in A$ means that you can connect the two rightmost wires.

$\endgroup$
  • $\begingroup$ I find the first paragraph rather hard to follow (again, I'm not sure the analogy is very enlightening) but a definite +1 for the rest of the answer. $\endgroup$ – David Richerby Nov 14 '17 at 18:40

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.