归约 百科内容来自于: 百度百科

英文

Reduction

定义

归约是使用解决其它问题的"黑盒"来解决另一个问题.

应用

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

结论

归约让我们理解两个问题间的关系,它是一种技术,用于寻找解决某个问题或它的变形.
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定