在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。

简介在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在多项式时间内（不考虑子程序运行所用时间）解决另一个问题的归约方法。多项式时间归约有几种不同类型，取决于具体如何使用子程序。

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

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

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

可以记为：X ≤p Y

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

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

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

- 假设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的点覆盖，那么就可以判定该顶点是最小点覆盖中的顶点，不断重复这个操作，就可以找到最小点覆盖。

本词条内容贡献者为:

张尉 - 副教授 - 西南大学