134
个编辑
更改
跳到导航
跳到搜索
小第241行：
第241行： − + 第247行：
第247行： − + 第260行：
第260行： − 以上所有讨论都假设P意味“容易”，而“不在P中”意味着“困难”，这一假设称为科巴姆论点。这是复杂性理论中一个常见且相当合理的假设；然而，它也有一些注意事项。+ − 首先，这在实际中并不总是正确的。理论上，多项式算法可能有非常大的常数因子或指数，因此并不切实际。例如，判定一个图G是否包含H作为副图，其中H是固定的，该问题可以在O（n2）的运行时间内解决，其中n是G中的顶点数，大O表示法隐藏了一个以超指数形式依赖于H的常数。该常数大于<math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math>（使用Knuth的uparrow表示法），其中h是H中的顶点数。+ − 另一方面，即使一个问题被证明是NP完全的并且P≠NP，在实践中仍然可能有高效的方法来解决这个问题。许多NP完全问题，如背包问题、旅行商问题和布尔可满足性问题，都有算法可以在合理的时间得到最优解。这类算法的实际平均案例复杂度（时间与问题大小）可能低得出奇。线性规划中的单纯形法就是这样一个例子，它在实际中的表现出奇地好；尽管在最坏情况下的时间复杂度是指数级的，与已知最好的算法一样是多项式时间算法。+
→P意味着“容易”？： 二轮
= = p 是“容易”的意思吗？= = 所有上述讨论都假定 p 意味着“容易”，而“不在 p 中”意味着“困难”，这一假设被称为 Cobham 的论点。在复杂性理论中，这是一个常见且相当准确的假设; 然而，它也有一些警告。
= = p 是“容易”的意思吗？= = 所有上述讨论都假定 p 意味着“容易”，而“不在 p 中”意味着“困难”，这一假设被称为 Cobham 的论点。在复杂性理论中，这是一个常见且相当准确的假设; 然而，它也有一些警告。
First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]], where ''H'' is fixed, can be solved in a running time of ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{cite journal |author1=Kawarabayashi, K. I. |author2=Kobayashi, Y. |author3=Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where ''n'' is the number of vertices in ''G''. However, the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than <math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (using [[Knuth's up-arrow notation]]), and where ''h'' is the number of vertices in ''H''.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>
First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]], where ''H'' is fixed, can be solved in a running time of ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{cite journal |author1=Kawarabayashi, K. I. |author2=Kobayashi, Y. |author3=Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where ''n'' is the number of vertices in ''G''. However, the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than <math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (using [[Knuth's up-arrow notation]]), and where ''h'' is the number of vertices in ''H''.<ref name=":22">{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>
First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of deciding whether a graph G contains H as a minor, where H is fixed, can be solved in a running time of O(n2), where n is the number of vertices in G. However, the big O notation hides a constant that depends superexponentially on H. The constant is greater than 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) (using Knuth's up-arrow notation), and where h is the number of vertices in H.
First, it is not always true in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, thus rendering it impractical. For example, the problem of deciding whether a graph G contains H as a minor, where H is fixed, can be solved in a running time of O(n2), where n is the number of vertices in G. However, the big O notation hides a constant that depends superexponentially on H. The constant is greater than 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) (using Knuth's up-arrow notation), and where h is the number of vertices in H.
首先，这在实践中并不总是正确的。一个理论上的多项式算法可能有非常大的常数因子或指数，从而使其不切实际。例如，判断一个图 g 是否包含 h 作为一个次项，其中 h 是固定的，这个问题可以在 o (n2)的运行时间内解决，其中 n 是 g 的顶点数。这个常数大于2个上行上行(2个上行上行(2个上行上行(h/2)))(使用 Knuth 的上箭头表示法) ，其中 h 是 h 中的顶点数。
首先，这在实践中并不总是正确的。一个理论上的多项式算法可能有非常大的常数因子或指数，从而使其不切实际。例如，判断一个图 g 是否包含 h 作为一个次项，其中 h 是固定的，这个问题可以在 o (n2)的运行时间内解决，其中 n 是 g 的顶点数。这个常数大于2个上行上行(2个上行上行(2个上行上行(h/2)))(使用 Knuth 的上箭头表示法) ，其中 h 是 h 中的顶点数。
On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the [[knapsack problem]], the [[traveling salesman problem]] and the [[Boolean satisfiability problem]], that can solve to optimality many real-world instances in reasonable time. The empirical [[average-case complexity]] (time vs. problem size) of such algorithms can be surprisingly low. An example is the [[simplex algorithm]] in [[linear programming]], which works surprisingly well in practice; despite having exponential worst-case [[time complexity]], it runs on par with the best known polynomial-time algorithms.<ref>{{cite book|last1=Gondzio|first1=Jacek|last2=Terlaky|first2=Tamás|chapter=3 A computational view of interior point methods |mr=1438311 |title=Advances in linear and integer programming|pages=103–144|editor=J. E. Beasley|location=New York|publisher=Oxford University Press|year=1996|series=Oxford Lecture Series in Mathematics and its Applications |volume=4 |chapter-url=http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps|id=[http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps Postscript file at website of Gondzio] and [http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz at McMaster University website of Terlaky]}}</ref>
On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the [[knapsack problem]], the [[traveling salesman problem]] and the [[Boolean satisfiability problem]], that can solve to optimality many real-world instances in reasonable time. The empirical [[average-case complexity]] (time vs. problem size) of such algorithms can be surprisingly low. An example is the [[simplex algorithm]] in [[linear programming]], which works surprisingly well in practice; despite having exponential worst-case [[time complexity]], it runs on par with the best known polynomial-time algorithms.<ref name=":23">{{cite book|last1=Gondzio|first1=Jacek|last2=Terlaky|first2=Tamás|chapter=3 A computational view of interior point methods |mr=1438311 |title=Advances in linear and integer programming|pages=103–144|editor=J. E. Beasley|location=New York|publisher=Oxford University Press|year=1996|series=Oxford Lecture Series in Mathematics and its Applications |volume=4 |chapter-url=http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps|id=[http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps Postscript file at website of Gondzio] and [http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz at McMaster University website of Terlaky]}}</ref>
On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem and the Boolean satisfiability problem, that can solve to optimality many real-world instances in reasonable time. The empirical average-case complexity (time vs. problem size) of such algorithms can be surprisingly low. An example is the simplex algorithm in linear programming, which works surprisingly well in practice; despite having exponential worst-case time complexity, it runs on par with the best known polynomial-time algorithms.
On the other hand, even if a problem is shown to be NP-complete, and even if P ≠ NP, there may still be effective approaches to tackling the problem in practice. There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem and the Boolean satisfiability problem, that can solve to optimality many real-world instances in reasonable time. The empirical average-case complexity (time vs. problem size) of such algorithms can be surprisingly low. An example is the simplex algorithm in linear programming, which works surprisingly well in practice; despite having exponential worst-case time complexity, it runs on par with the best known polynomial-time algorithms.
==P意味着“容易”？==
==P意味着“容易”？==
以上所有讨论都假设P意味“容易”，而“不在P中”意味着“困难”，这一假设称为科巴姆（Cobham）论点。这是复杂性理论中一个常见且相当合理的假设；但需要注意一些事情。
首先，这在实际中并不总是正确的。理论上，多项式算法可能有非常大的常数因子或指数项，这时假设失效。例如，判定一个图''G''是否包含子图''H''，其中''H''是确定的。该问题可以在''O(n<sup>2</sup>)''的运行时间内解决，<ref name="kkr12" />其中''n''是''G''中的顶点数，大O表示法隐藏了一个以超指数形式依赖于''H''的常数。该常数大于<math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math>（使用Knuth的上箭头表示法），其中''h''是''H''中的顶点数。<ref name=":22" />
另一方面，即使一个问题被证明是NP完全的并且P ≠ NP，在实际中仍然可能有高效的方法来解决这个问题。许多NP完全问题，如背包问题、旅行商问题和布尔可满足性问题，都有算法可以在合理的时间得到最优解。这类算法的平均复杂度（时间与问题规模大小）可能低得出奇。线性规划中的单纯形法就是这样一个例子，它在实际中的表现出奇地好，与已知最好的算法一样是多项式时间算法，尽管在最坏情况下的时间复杂度是指数级的。<ref name=":23" />
最后，还有一些类型的计算比如量子计算和随机算法不符合图灵机模型，P和NP是在图灵机模型上定义的，。
最后，还有一些类型的计算比如量子计算和随机算法不符合图灵机模型，P和NP是在图灵机模型上定义的，。