《计算复杂性：现代方法》——2.4　归约网络

本节书摘来自华章计算机《计算复杂性：现代方法》一书中的第2章，第2.4节，作者 ［美］桑杰夫·阿罗拉（Sanjeev Arora），博阿兹·巴拉克（Boaz Barak），译 骆吉洲，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4　归约网络

回顾一下第0章中的如何安排晚宴以确保任意一对宾客之间均能和睦相处的问题，例0.1将该问题形式化为如下的语言：

归约的赞誉

虽然多项式时间归约概念（以及它的第一个孪生概念——随机多项式时间归约，将在7.6节给出定义）的提出源于NP完全性理论，然而由此引出的对复杂性理论的理解远远超出了NP完全性本身。如今，复杂性理论和密码学（因而本书的许多章节）的相当一部分工作是利用归约为不同的复杂性理论猜想建立联系。为什么复杂性理论学家均擅长于使用归约，而不擅长于踏踏实实地证明图灵机的下界呢？或许这是由于，他们的创造性更适于创造精巧的构件和设计算法（毕竟，归约只是将一个问题转换为另一个问题的算法），而不是证明图灵机的下界。