patternModerate
What is a "reduction", really?
Viewed 0 times
reallyreductionwhat
Problem
I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..."
What exactly does "to reduce" mean? I can't draw the picture in my head. Can anyone can help me understand this definition?
What exactly does "to reduce" mean? I can't draw the picture in my head. Can anyone can help me understand this definition?
Solution
This is kind of a broad question, and there are a lot of well-written references. This answer is just a basic starting point.
Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we know that $A$ is unsolvable (according to some fitting notion of unsolvability), then $B$ is also unsolvable.
In undergrad computability course, we usually talk about mapping reductions. A mapping reduction from $A$ to $B$ is a computable function $f:\Sigma^\to \Sigma^$, such that for all $x\in \Sigma^*$ it holds that $x\in A$ iff $f(x)\in B$.
The intuition behind this definition is that, assuming we have an algorithm that solves $B$, then we can solve $A$. Indeed, given an input for $A$, we use the reduction $f$ to transform it to an input for $B$, and solve $B$ using our algorithm. The "iff" property of the reduction ensures that the answer we get on $B$ induces an answer for $A$.
As a concrete example, let's consider the halting problem: given a TM $M$ and input $w$, decide whether $M$ halts in its run on $w$.
We want to reduce $A_{TM}$ to the halting problem. That is, we want to show that if we could solve the halting problem, then $A_{TM}$ is also solvable. So what we need to show is a function that takes an input $M,w$ for $A_{TM}$, and transforms it into an input $M',w'$ for the halting problem, such that the $M$ accepts $w$ iff $M'$ halts on $w'$.
We do this as follows. Given input $M,w$, construct $M'$ to be the machine that behaves exactly like $M$, except that we replace the rejecting state of $M$ with a self-loop (that never halts). We then output $M',w$. Now, it is not hard to prove that $M$ accepts $w$ iff $M'$ halts on $w$, and thus we have a reduction. Also note that this reduction is computable, since computing $M'$ from $M$ is a simple matter of changing the behavior of a state.
Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we know that $A$ is unsolvable (according to some fitting notion of unsolvability), then $B$ is also unsolvable.
In undergrad computability course, we usually talk about mapping reductions. A mapping reduction from $A$ to $B$ is a computable function $f:\Sigma^\to \Sigma^$, such that for all $x\in \Sigma^*$ it holds that $x\in A$ iff $f(x)\in B$.
The intuition behind this definition is that, assuming we have an algorithm that solves $B$, then we can solve $A$. Indeed, given an input for $A$, we use the reduction $f$ to transform it to an input for $B$, and solve $B$ using our algorithm. The "iff" property of the reduction ensures that the answer we get on $B$ induces an answer for $A$.
As a concrete example, let's consider the halting problem: given a TM $M$ and input $w$, decide whether $M$ halts in its run on $w$.
We want to reduce $A_{TM}$ to the halting problem. That is, we want to show that if we could solve the halting problem, then $A_{TM}$ is also solvable. So what we need to show is a function that takes an input $M,w$ for $A_{TM}$, and transforms it into an input $M',w'$ for the halting problem, such that the $M$ accepts $w$ iff $M'$ halts on $w'$.
We do this as follows. Given input $M,w$, construct $M'$ to be the machine that behaves exactly like $M$, except that we replace the rejecting state of $M$ with a self-loop (that never halts). We then output $M',w$. Now, it is not hard to prove that $M$ accepts $w$ iff $M'$ halts on $w$, and thus we have a reduction. Also note that this reduction is computable, since computing $M'$ from $M$ is a simple matter of changing the behavior of a state.
Context
StackExchange Computer Science Q#10393, answer score: 13
Revisions (0)
No revisions yet.