当通过减少已知复杂性的现有问题来证明新问题的下限时，重点在于线性时间的减少。我有点猜测，如果没有线性时间（例如ωn ^ 2）的减少，我们将无法比较这两个问题。但是怎么说呢？
也可以说，已知问题是Ωn ^ 3。现在，Ωn ^ 2的减少是否可以安全地证明未知问题具有n ^ 3的复杂度？
这里是正式声明。
假设问题类型A可以在O(f(n)的时间内解决。
假设问题B可以在时间O(g(n))上减少为大小为h(n)的问题。
然后我们可以在B的时间内解决问题O(g(n) + f(h(n)))。
理想情况下，我们希望减少速度要快，并且问题不会太大。通常，做不到比减少线性时间更好的方法，因为它仅需要线性时间即可解决问题。这就是为什么这是理想的。
注意，如果f(n)具有多项式上限，则可以将“大小为h(n)的问题”放宽为“大小为O(h(n))的问题”。这通常是正确的，并且可以节省很多精力。但是，这种简化失败的示例是f(n) = 2^n和h(n) = n+log(n))。