Reduction
归约是使用解决其它问题的"黑盒"来解决另一个问题.
假设有一个复杂的问题P,而它看起来与一个已知的问题Q很相似,可以试着在两个问题间找到一个归约(reduction, 或者transformation).
对于问题的先后,归约可以达到两个目标:
(1)已知Q的算法,那么就可以把使用了Q的黑盒的P的解决方法转化成一个P的算法.
(2)如果P是一个已知的难题,或者特别地,如果P的下限,那么同样的下限也可能适用于Q.前一个归约是用于获取P的信息;而后者则是用于获取Q的信息.
归约让我们理解两个问题间的关系,它是一种技术,用于寻找解决某个问题或它的变形.