在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。如果将第一个问题转换成第二个问题的时间，且子程序被调用的次数都是多项式级别的，那么第一个问题可以多项式时间归约到第二个问题。多项式时间归约证明了第一个问题不比第二个问题难，因为当第二个问题存在高效率算法时，第一个也存在。反之，如果第一个问题没有高效率算法时，第二个也没有。计算复杂性理论中经常使用多项式时间归约来定义复杂性类和完全问题。

多项式时间归约：如果问题X和问题Y满足以下两条性质，那么问题X可以在多项式时间归约到问题Y。

- 问题X可以通过多项式时间的基本运算步骤转换为问题Y；

- 问题X多项式次调用求解问题Y的算法，且问题Y可以在多项式时间内被求解。

可以记为：X ≤p Y

需要注意的是，问题X转换为问题Y之后，问题Y的运行时间是建立在问题Y的输入上。

对于这个定义，可以简单理解为：求解问题Y算法需要多项式时间，问题X转换为问题Y需要多项式个基本运算加上多项式次调用求解问题Y的算法。因此总共需要的时间是：多项式 + 多项式 * 多项式。

多项式时间归约有几种不同类型，取决于具体如何使用子程序。三种最常见的多项式时间归约类型，从最多限制到最少限制的，是多项式时间多一归约（Karp归约）、真值表归约和图灵归约（Cook归约）。

多一归约（Karp归约）是将问题A的输入转换成问题B的输入的多项式算法，使得转换后的问题与原问题有相同的输出。问题A的实例x可以通过此转换为问题B的实例y，将y输入解决问题B的算法，然后返回它的输出。

真值表归约是将问题A的输入转换成固定数量个问题B的输入的多项式算法，使得原问题的输出可以被表示为问题B输出的函数。将B的输出映射到A的输出的函数对于所有输入必须相同，所以它可以用真值表表示。

图灵归约（Cook归约）是一种算法，它需要调用问题B的子程序多项式次，以及这些子程序调用之外的多项式时间来解决问题A。多一归约可以被视为图灵归约的受限变体，其中对问题B的子程序的调用次数恰好为1，且归约返回的值与子程序返回的值相同。

根据以上定义，可以得到三个定理：

- 假设X ≤p Y，如果Y能够在多项式时间内求解，那么X也能在多项式时间内求解。

- 假设X ≤p Y，如果X不能在多项式时间内求解，那么Y也不能在多项式时间内求解。

- 如果X ≤p Y且Y ≤p X，那么X和Y是等价的。

归约的几种技巧：

1. 简单的恒等归约：比如最大独立集和最小点覆盖。

2. 从特殊情况到一般情况：比如点覆盖 ≤p 集合覆盖。

3. 利用gadgets：比如3-SAT ≤p 独立集。

自归约：将求解问题归约成判断问题，如果判断问题能够解决，那么就可以利用判断问题来解决求解问题。

比如最小点覆盖问题，假如我们能判断一个图中是否存在点数为k的最小点覆盖。于是可以遍历图中的每个顶点，如果删去这个顶点以及和这个顶点相连接的边，图中只存在点数为k-1的点覆盖，那么就可以判定该顶点是最小点覆盖中的顶点，不断重复这个操作，就可以找到最小点覆盖。