先深后广，厚积而薄发
归约
上一篇 /
下一篇 2012-02-04 22:07:35
/ 个人分类：学习方法
来自百度百科和维基百科
我们解题时常遇见似曾相识的题目。此时，我们若可将新题转换成已解旧题的一例，则新题亦解矣。
另一更微妙的用法是：若我们拥有一个已证明难以解决的问题，我们又获得另一个相似的新问题。我们可合理推想此新问题亦是难以解决的。我们可由下列谬证法得证：若此新问题本质上容易解答，且若我们可展示每个旧问题的实例可经由一系列转换步骤变成新问题的实例，则旧问题便容易解决，因此得到悖论。因此新问题可知亦难以解决。
定义：
归约是使用解决其它问题的"黑盒"来解决另一个问题.
应用：
假设有一个复杂的问题P,而它看起来与一个已知的问题Q很相似,可以试着在两个问题间找到一个归约(reduction, 或者transformation).
对于问题的先后,归约可以达到两个目标:
(1)已知Q的算法,那么就可以把使用了Q的黑盒的P的解决方法转化成一个P的算法.
(2)如果P是一个已知的难题,或者特别地,如果P的下限,那么同样的下限也可能适用于Q.前一个归约是用于获取P的信息;而后者则是用于获取Q的信息.
结论：
归约让我们理解两个问题间的关系,它是一种技术,用于寻找解决某个问题或它的变形.
收藏
举报
TAG:
归约
