A language A is mapping reducible to language B, written as A \leq_{m} B, if there is a computable function f: \Sigma^{*} \to \Sigma ^{ *} such that for every w, w \in A \Leftrightarrow f(w) \in B. This is sometimes called a “many-to-one” reduction because often times you want to have multiple w mapping to the same f(w). We remember this as “A is weaker (“not stronger”) than B”; or “A is reducable to B” Recipe For some A \leq_{M} B, we have three mechanical parts: there exists some computable function f from \Sigma^{*} \to \Sigma^{*} which should take x \in A \Leftrightarrow f(x) \in B General idea prove a language L is undecidable by proving that if L is decidable, so is A_{TM}. In particular, we reduce A_{TM} to the language L (i.e. make a machine for A_{TM} from L — A_{TM} \leq_{M} L). computable function a function f: \Sigma^{*} \to \Sigma^{ *} is a computable function if there is a turing machine M which halts with just f(w) written on its tape, for every input w. the function returns the tape after M halts. additional info polynomial time mapping reduction polynomial time mapping reduction is a mapping reduction!
but we also say that f is both computable AND polynomial: that there exists a Polynomial Time turing machine M that, on every input, halts with f(w) on the tape within a polynomial number of steps on w. If w \in A \Leftrightarrow f(w) \in B, we have that f is a polynomial time mapping reduction. Note that since M is bounded by a polynomial number of steps, we also have |f(w)| \leq |w|^{k} by some polynomial number of steps since the machine M can’t take more steps than polynomial so it can’t generate super long strings. Note, that this is still a normal mapping reduction, that is, we have reduced the problem of deciding w \in A to that of decidnig f(w) \in B. The usual rules of mapping reduction still applies: if A \leq_{p} B, and B \leq_{p} C, we have A \leq_{p} C The important properties about this is that if some string n \in A, after all the reduction we still have a polynomial time strings f(f(n)) would be length n^{cd} which would be a polynomially bounded computation with also bounded output length. timing properties of reduction \begin{equation} A \leq_{p} B, B \in P \implies A \in P \end{equation} because you can solve A by sending a string through f, decide it with B, then you have decided A since w \in A \Leftrightarrow f(w) \in B; if B is decidable in P and f(w) is computable in P, well then A have just been decided in P same idea
and of course the contrapositives:
mapping reductions are transitive if A \leq_{m} B, and B \leq_{m} C, we have A \leq_{m} C examples halting problem \begin{equation} HALT_{TM} = \left{(M,w) \mid M\text{ is a TM \hat{t} halts on the string } w\right} \end{equation} This is undecidable! Assume for contradiction that there is some H for which it decides HALT_{TM}. Now: we can actually use this property to construct a TM that decides A_{TM}, which we have already seen that there are non-recognizable languages so that’s not possible. In particular, we check if H(M, w); then, we run M on w until it halts—if accept, return accept; if reject, return reject; if H(M,w) says it won’t halt, then reject. Then, we just made a machine that decides A_{TM}, yet A_{TM} is recognizable but not decidable. With a reduction, we see that halting problem is undecidable. if A <= B, B is decidable, then A is decidable To decide A, we build a machine M’, where by we first: Compute f(w) on some given string w Then, run M (which decides B) on f(w), return its results w \in A \Leftrightarrow f(w) \in B, so if M accepts f(w) we know w \in A w\not \in A, then we will have f(w) \not \in B, and so M’ will reject w if A <= B, B is recognizable, then A is recognizable same as above—if you get the answer, let m’ return it. otherwise, we run forever. contrapositives of the above if A <= B, if A is undecidable, then B is undecidable if A <= B, if A is unrecognizable, then B is unrecognizable “A gives a lower bound on the difficulty of B” Atm <= HaltTM halting problem things to map to Atm is recognizable but not decidable not ATM is not recognizable because ATM is not decidable HALT_TM is recognizable but not decidable EmptyTM is not recognizable EqualTM (if a pair of TM is equal) is not recognizable if A <= B, if A is undecidable, then B is undecidable if A <= B, if A is unrecognizable, then B is unrecognizable if A <= B, B is decidable, then A is decidable