patternModerate
The 'directionality' of reductions?
Viewed 0 times
reductionsthedirectionality
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#83903, answer score: 19
Revisions (0)
No revisions yet.