图灵归约 Turing Reduction
把还没解决的问题归约到已经解决的问题上
用已经解决的问题去解决还没解决的问题
密码学原理与实践 Page 167
假设我们已经存在一个解决问题 A 的算法 $G(x)$
一个A到B的图灵归约即利用$G(x)$构造一个解决问题B的算法$H(x)$, 并且$H(x)$是多项式时间的.
https://zhuanlan.zhihu.com/p/194313998 这篇文章译自 reductions-and-jokes
一个物理学家和一个数学家正坐在教师休息室里。突然间，休息室里的咖啡机着火了。物理学家就拿了一个垃圾桶，把里面的垃圾清空，跑到水池前，给垃圾桶灌满水，随后扑灭了火。由于这个咖啡机着过一次火了，大家都同意把垃圾桶装满水放在这个咖啡机旁边。
第二天，同样的两个人又坐在同样的休息室里，咖啡机又一次着火了。这一次，数学家站了起来，把装满水的垃圾桶拿了起来，把里面的水倒掉，又放了一些垃圾在里面，交给了物理学家。这样就把问题归约到了一个之前已经解决过的问题上。虽然这个笑话是讽刺数学家的，但确实很好地解释了归约这个概念。其想法很简单：我们现在遇到了个问题，可以把它转化到一个某个已解决的问题上，而不是一定要直接解决这个问题。从这个意义上来说，归约其实是一种比较懒的解决问题的方式。
Instead of putting out a fire, the following video is about retrieving a shoe that is floating away.
# Another Example
Here is an example of reductions that are not so silly and a little less simple.
Imagine that Alice and Bob are at it again. Bob wants to be able to multiply integers fast and he plans on building a hardware system that stores the answers in a table. Then his hardware system will be able to compute the product of two integers by just looking up the answers. Okay, there are really better ways to do this, but just play along for the moment.
Bob’s table is big and he is troubled. The above table has
entries just to multiply numbers less than
. Clearly for a more extensive table the cost grows fast. He asks his friend Alice for some help. She says:”Just store the diagonal values and I can show you how to handle the general case.” Here is her old trick.
Using this allows Bob to just store the diagonal of the multiplication table, and forget all the rest. It is a powerful reduction that shows:
One can reduce integer multiplication to addition and taking the square of a number.
For example,
