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