1.虽然把所需运行时间Θ(n^100)的问题作为难处理问题也是合理的，但实际中需要如此高次的多项式时间的问题是非常少的。在实际中，所遇到的典型多项式时间可解问题所需要的时间要少得多。经验表明：一旦一个问题的多项式算法被发现，往往就能发现一些更为有效的算法。
2.对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。我们讨论的大多数使用串行随机存取计算机在多项式时间内能解决的问题类，与抽象的图灵机在多项式时间内可求解的问题是相同的，它与利用并行计算机在多项式时间内可求解的问题类相同。即使处理器数目随输入规模以多项式增加也是这样。
3.多项式时间可解问题类是封闭的。在加法、乘法的组合运算下，多项式是封闭的。例如：一个多项式时间的算法作为另一个多项式时间算法的输入，得到的算法也是多项式时间算法。（O(n^x)+O(n^y) = O(n^x), x>y ）如果另外一个多项式算法对一个多项式时间的子程序进行常数次调用，那么组合算法的运行时间也是多项式的。（O(n^x)*O(n^y)=O(n^(x+y))）
2.对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。我们讨论的大多数使用串行随机存取计算机在多项式时间内能解决的问题类，与抽象的图灵机在多项式时间内可求解的问题是相同的，它与利用并行计算机在多项式时间内可求解的问题类相同。即使处理器数目随输入规模以多项式增加也是这样。
3.多项式时间可解问题类是封闭的。在加法、乘法的组合运算下，多项式是封闭的。例如：一个多项式时间的算法作为另一个多项式时间算法的输入，得到的算法也是多项式时间算法。（O(n^x)+O(n^y) = O(n^x), x>y ）如果另外一个多项式算法对一个多项式时间的子程序进行常数次调用，那么组合算法的运行时间也是多项式的。（O(n^x)*O(n^y)=O(n^(x+y))）
No comments:
Post a Comment