2
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.