计算复杂性理论 - 版本历史

2021年3月2日 (二) 07:47 Sizuka

2021-03-02T07:47:49Z

显示更改

2020年12月6日 (日) 15:15 水流心不竞

2020-12-06T15:15:41Z

2020年12月6日 (日) 15:07 水流心不竞

2020-12-06T15:07:02Z

显示更改

水流心不竞：/* History历史 */

2020-11-18T17:13:32Z

History历史

2020年11月18日 (三) 17:10 水流心不竞

2020-11-18T17:10:10Z

2020年11月18日 (三) 17:01 水流心不竞

2020-11-18T17:01:58Z

水流心不竞：/* Separations between other complexity classes其他复杂性类之间的分离 */

2020-11-18T17:00:04Z

Separations between other complexity classes其他复杂性类之间的分离

水流心不竞：/* Problems in NP not known to be in P or NP-completeNP中不知是P或NP完全问题的问题 */

2020-11-18T16:55:54Z

Problems in NP not known to be in P or NP-completeNP中不知是P或NP完全问题的问题

水流心不竞：/* Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题 */

2020-11-18T16:50:54Z

Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题

2020年11月18日 (三) 16:50 水流心不竞

2020-11-18T16:50:00Z

显示更改

@@ 第1,214行： / 第1,214行： @@
 Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ''n''<sup>15</sup>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ''n''<sup>3</sup> or ''n''<sup>2</sup> algorithms are often impractical on realistic sizes of problems.
-类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”<sup>15</sup>，那么认为它是有效的是不合理的，而且除了在小实例上，它仍然是无用的。实际上，在实践中，即使是''n''<sup>3</sup> 或 ''n''<sup>2</sup> 算法对于实际大小的问题往往是不切实际的。
+类似地，多项式时间算法并不总是实用的。如果它的运行时间是，比如说“n”<sup>15</sup>，那么认为它有效是不合理的，而且除了在小的实例上，它仍旧是无用的。实际上，在实践中，即使是''n''<sup>3</sup> 或 ''n''<sup>2</sup> 算法对于实际大小的问题也往往是不切实际的。
 ==Continuous complexity theory连续复杂性理论==

@@ 第1,255行： / 第1,255行： @@
 In 1967, [[Manuel Blum]] formulated a set of [[axiom]]s (now known as [[Blum axioms]]) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called [[Blum's speedup theorem|speed-up theorem]]. The field began to flourish in 1971 when the [[Stephen Cook]] and [[Leonid Levin]] [[Cook–Levin theorem|proved]] the existence of practically relevant problems that are [[NP-complete]]. In 1972, [[Richard Karp]] took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse [[combinatorics|combinatorial]] and [[graph theory|graph theoretical]] problems, each infamous for its computational intractability, are NP-complete.<ref>{{Citation | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | title = Complexity of Computer Computations |editor= R. E. Miller |editor2=J. W. Thatcher| publisher = New York: Plenum | pages = 85–103 | year = 1972}}</ref>
-年，[[Manuel Blum]]提出了一组[[公理]]s（现在称为[[Blum axioms]]），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的[[Blum加速定理|加速定理]]。这个领域在1971年开始蓬勃发展，当时[[Stephen Cook]]和[[Leonid Levin]][[Cook–Levin定理|证明了[[NP complete]]实际相关问题的存在。1972年，[[Richard Karp]]以其里程碑式的论文《组合问题中的可还原性》（Reductibility In Combinational Problems）将这一想法向前推进了一大步，在这篇论文中，他展示了21个不同的[[组合学|组合]]和[[图论|图论]]问题，每一个都因其计算难处理而臭名昭著，是NP完全的。<ref>{引文{author=Richard M.Karp | chapter=组合问题之间的可约性|章url=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf|title=计算机计算的复杂性
+年，[[Manuel Blum]]提出了一组[[公理]]s（现在称为[[Blum axioms]]），规定了可计算函数集合上复杂性测度的理想性质，并证明了一个重要结果，即所谓的[[Blum加速定理|加速定理]]。这个领域在1971年开始蓬勃发展，当时[[Stephen Cook]]和[[Leonid Levin]][[Cook–Levin定理|证明了[[NP complete]]实际相关问题的存在。1972年，[[Richard Karp]]以其里程碑式的论文《组合问题中的可还原性》（Reductibility In Combinational Problems）将这一想法向前推进了一大步，在这篇论文中，他展示了21个不同的[[组合学|组合]]和[[图论|图论]]问题，每一个都因其计算难处理而声名狼藉，是NP完全的。<ref>{{Citation | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | title = Complexity of Computer Computations |editor= R. E. Miller |editor2=J. W. Thatcher| publisher = New York: Plenum | pages = 85–103 | year = 1972}}</ref>
 In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case{{cn|reason=passive, no source|date=August 2019}}, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=[https://archive.org/details/newkindofscience00wolf/page/1143 1143]|isbn=978-1-57955-008-0|url-access=registration|url=https://archive.org/details/newkindofscience00wolf/page/1143}}</ref>

@@ 第1,159行： / 第1,159行： @@
 A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
-在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> 相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
+在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
 Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.

@@ 第1,159行： / 第1,159行： @@
 A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
-在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft，J.e.，Motwani，R.和Ullman，J.D.（2007）[[自动机理论导论，语言，而计算]]，Addison-Wesley，Boston/San-Francisco/newyork（第368页）</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
+在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> 相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
 Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.

@@ 第1,125行： / 第1,125行： @@
 Along the same lines, '''[[co-NP]]''' is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of '''NP''' problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that '''NP''' is not equal to '''co-NP'''; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then '''P''' is not equal to '''NP''', since '''P'''='''co-P'''.  Thus if '''P'''='''NP''' we would have '''co-P'''='''co-NP''' whence '''NP'''='''P'''='''co-P'''='''co-NP'''.
-“是的，问题的答案与‘NP’的问题是相反的。据信<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/博阿斯·巴拉克关于计算复杂性的课程][http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf“NP”不等于“co-NP”，但它还没有被证明。很明显，如果这两个复杂度类不相等，那么“P”就不等于“NP”，因为“P”=“co-P”。因此，如果''P''=''NP''，我们将有''co-P'''=''co-NP''，其中''NP'''=''P''=''co-P'''=''co-NP''。
+“是的，问题的答案与‘NP’的问题是相反的。据信<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> “NP”不等于“co-NP”，但它还没有被证明。很明显，如果这两个复杂度类不相等，那么“P”就不等于“NP”，因为“P”=“co-P”。因此，如果''P''=''NP''，我们将有''co-P'''=''co-NP''，其中''NP'''=''P''=''co-P'''=''co-NP''。
 Similarly, it is not known if '''L''' (the set of all problems that can be solved in logarithmic space) is strictly contained in '''P''' or equal to '''P'''. Again, there are many complexity classes between the two, such as '''NL''' and '''NC''', and it is not known if they are distinct or equal classes.

@@ 第1,097行： / 第1,097行： @@
 Tractable problems are frequently identified with problems that have polynomial-time solutions (P, PTIME); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If NP is not the same as P, then NP-hard problems are also intractable in this sense.
-易处理的问题经常被认为是具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 '''<font color="#ff8000"> 退出时间难题extime-hard</font>'''。如果 NP 不等于 P，那么 '''<font color="#ff8000"> NP 难问题</font>'''在这个意义上也是棘手的。
+易处理的问题经常被认为是与具有多项式时间解决方案的问题(P，PTIME)相提并论; 这就是所谓的 Cobham-Edmonds 理论。在这个意义上被认为是棘手的问题包括那些 '''<font color="#ff8000"> 退出时间难题extime-hard</font>'''。如果 NP 不等于 P，那么 '''<font color="#ff8000"> NP 难问题</font>'''在这个意义上也是棘手的。
@@ 第1,107行： / 第1,107行： @@
 However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.
-然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。
+然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至不能说大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。
 ===Separations between other complexity classes其他复杂性类之间的分离===

@@ 第1,030行： / 第1,030行： @@
-===Problems in NP not known to be in P or NP-completeNP中不知是P中或NP完全问题的问题===
+===Problems in NP not known to be in P or NP-completeNP中不知是P或NP完全问题的问题===
 The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math> to factor an odd integer n. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.
@@ 第1,108行： / 第1,108行： @@
 然而，这种区别是不确切的：具有大的阶数或大的超前系数的多项式时间解增长很快，对于实际规模的问题可能不切实际；相反，缓慢增长的指数时间解在实际输入上却可能是实际的，或者在最坏情况下需要很长时间的解可能在大多数情况下只需要很短的时间，因此还是一般情况下实用的。说一个问题不在P中并不意味着问题的所有大型案例都是困难的，甚至大多数都是困难的。例如，Presburger算法中的决策问题被证明不在P中，然而在大多数情况下，已经编写了在合理时间内解决该问题的算法。类似地，算法可以在小于二次的时间内解决大范围的'''<font color="#ff8000"> NP完全背包问题</font>'''，而SAT解算器通常能处理NP完全'''<font color="#ff8000"> 布尔可满足性问题</font>'''的大量实例。
 ===Separations between other complexity classes其他复杂性类之间的分离===