370
个编辑
更改
跳到导航
跳到搜索
第127行：
第127行： − + − 确定性模型 − 第142行：
第140行： − + − 非确定性计算 − 第159行：
第155行： − + − 并行和分布式计算 − − {{main|Parallel computing|Distributed computing}} − − 并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布计算中，数据传输通过'''<font color="#ff8000">网络 network</font>'''完成，因此速度要慢得多。+ − − 第176行：
第166行： − + 第185行：
第175行： − + − 量子计算 − − + − − 第200行：
第186行： − + − + − 问题复杂度(下限) 第210行：
第195行： − + − − 第218行：
第201行： − 由此可见，用'''<font color="#ff8000">大O符号 big O notation</font>'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。+ − − 第226行：
第207行： − 另一方面，问题复杂度的非平凡下界一般难以获得，并且获得这种下界的方法很少。+ − − 第242行：
第221行： − 一些问题的解答可能是非常大的，特别是'''<font color="#ff8000">计算机代数 computer algebra</font>'''和'''<font color="#ff8000">计算代数几何 computational algebraic geometry</font>'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''<font color="#ff8000">{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates </font>'''可能有多达 <math>d^n</math>个复解(这是'''<font color="#ff8000">贝佐定理 Bézout's theorem</font>''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n).</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。+
→Parallel and distributed computation
复杂度的评估依赖于'''<font color="#ff8000">计算模型 model of computation</font>'''的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。
复杂度的评估依赖于'''<font color="#ff8000">计算模型 model of computation</font>'''的选择，包括定义在一个时间单位内完成的基本操作。当没有明确指定时，默认使用的计算模型是'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。
===Deterministic models===
===确定性模型===
A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[Random access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s.
A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[Random access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s.
当计算模型没有被指定时，通常假设它是一个'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
当计算模型没有被指定时，通常假设它是一个'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
===Non-deterministic computation===
===非确定性计算===
In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).
In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time is the time spent by the first processor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).
如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为'''<font color="#ff8000"> NP完全问题 NP-complete</font>'''。许多'''<font color="#ff8000">组合 combinatorial</font>'''问题，例如'''<font color="#ff8000">背包问题 Knapsack problem</font>'''、'''<font color="#ff8000">旅行推销员问题 travelling salesman problem</font>'''和'''<font color="#ff8000">布尔可满足性问题 Boolean satisfiability problem</font>'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP，既。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。
如果一个问题属于 NP 问题，且不比其他任何 NP 问题简单，则称该问题为'''<font color="#ff8000"> NP完全问题 NP-complete</font>'''。许多'''<font color="#ff8000">组合 combinatorial</font>'''问题，例如'''<font color="#ff8000">背包问题 Knapsack problem</font>'''、'''<font color="#ff8000">旅行推销员问题 travelling salesman problem</font>'''和'''<font color="#ff8000">布尔可满足性问题 Boolean satisfiability problem</font>'''都是NP完全问题。对于所有这些问题，最著名的算法具有指数复杂度。如果这些问题中的任何一个都可以在确定性机器上在多项式时间内求解，那就意味着所有 NP 问题都可以在多项式时间内求解，我们立即可以得出结论：P = NP，既。一般认为P类问题和NP类问题是等价的，即所有NP类问题都有在确定性图灵机上以多项式时间解决的方法。现在我们主要的猜想是，NP 问题的最坏情况本质上是难以解决的，即 <math>P \neq NP</math>。
===Parallel and distributed computation===
===并行和分布式计算===
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a [[computer network|network]] and is therefore much slower.
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a [[computer network|network]] and is therefore much slower.
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower.
Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a network and is therefore much slower.
并行处理器和分布式计算处理器由同时工作的多个处理器组成。不同模型之间的差异主要体现在处理器之间的信息传输方式上。通常情况下，在并行计算中处理器之间的数据传输非常快，而在分布式计算中，数据传输通过'''<font color="#ff8000">网络</font>'''完成，因此速度要慢得多。
The time needed for a computation on {{mvar|N}} processors is at least the quotient by {{mvar|N}} of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
The time needed for a computation on {{mvar|N}} processors is at least the quotient by {{mvar|N}} of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
The time needed for a computation on processors is at least the quotient by of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
The time needed for a computation on processors is at least the quotient by of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.
在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。事实上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。
在{{mvar|N}}个处理器上进行计算所需的时间至少是单个处理器所需时间的{{mvar|N}}的商。但实际上，这个理论上的最优界限永远不可能达到，由于有些子任务不能并行化，部分处理器不得不先等待另一个处理器的结果。
因此，主要的复杂度问题是如何设计算法，使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。
因此，主要的复杂度问题是如何设计算法，使得计算时间与处理器数量的乘积尽可能接近在单个处理器上进行同一计算所需的时间。
===Quantum computing===
===量子计算===
A [[quantum computer]] is a computer whose model of computation is based on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
A [[quantum computer]] is a computer whose model of computation is based on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
A quantum computer is a computer whose model of computation is based on quantum mechanics. The Church–Turing thesis applies to quantum computers; that is, every problem that can be solved by a quantum computer can also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower time complexity using a quantum computer rather than a classical computer. This is, for the moment, purely theoretical, as no one knows how to build an efficient quantum computer.
'''<font color="#ff8000">量子计算机 quantum computer</font>'''是一种计算模型是基于'''<font color="#ff8000">量子力学 quantum mechanics</font>'''的计算机。'''<font color="#ff8000">丘奇-图灵理论 Church–Turing thesis</font>'''适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题理论上可以用量子计算机而不是传统计算机来解决，并且'''<font color="#ff8000">时间复杂度 time complexity</font>'''要低得多。由于没有人知道如何建造一台高效的量子计算机，目前这纯粹是理论上可行的。
'''<font color="#ff8000">量子计算机 quantum computer</font>'''是一种基于'''<font color="#ff8000">量子力学 quantum mechanics</font>'''的计算机。'''<font color="#ff8000">丘奇-图灵理论 Church–Turing thesis</font>'''适用于量子计算机，也就是说，任何可以由量子计算机解决的问题也可以由图灵机解决。然而，有些问题理论上可以用量子计算机以极低的'''<font color="#ff8000">时间复杂度 time complexity解决，而用传统图灵机则无法解决</font>'''。由于没有人知道如何建造一台高效的量子计算机，目前这纯粹只是理论上可行的。
[[Quantum complexity theory]] has been developed to study the [[complexity class]]es of problems solved using quantum computers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that are resistant to attacks by quantum computers.
[[Quantum complexity theory]] has been developed to study the [[complexity class]]es of problems solved using quantum computers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that are resistant to attacks by quantum computers.
Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post-quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers.
Quantum complexity theory has been developed to study the complexity classes of problems solved using quantum computers. It is used in post-quantum cryptography, which consists of designing cryptographic protocols that are resistant to attacks by quantum computers.
'''<font color="#ff8000">量子复杂度理论 Quantum complexity theory</font>'''已经发展到研究用量子计算机解决的问题的'''<font color="#ff8000">复杂度类 complexity class</font>'''。它用于'''<font color="#ff8000">后量子密码学 post-quantum cryptography</font>'''，其中包括设计能抵御量子计算机攻击的'''<font color="#ff8000">安全协议 cryptographic protocol</font>'''。
'''<font color="#ff8000">量子复杂度理论 Quantum complexity theory</font>'''研究用量子计算机解决的问题的'''<font color="#ff8000">复杂度类</font>'''。它主要用于'''<font color="#ff8000">后量子密码学 post-quantum cryptography</font>'''，包括设计能抵御量子计算机攻击的'''<font color="#ff8000">安全协议 cryptographic protocol</font>'''。
==Problem complexity (lower bounds)==
==问题复杂度(下限)==
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.
问题的复杂度是解决问题算法(包括未知算法)复杂度的'''<font color="#ff8000">下确界 infimum</font>'''。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。
问题的复杂度是解决问题算法(包括未知算法)复杂度的'''<font color="#ff8000">下确界 infimum，</font>'''即解决这个问题所需的最少时间。因此，问题的复杂度比任何解决该问题的算法的复杂度都要小。
It follows that every complexity that is expressed with [[big O notation]] is a complexity of the algorithm as well as of the corresponding problem.
It follows that every complexity that is expressed with [[big O notation]] is a complexity of the algorithm as well as of the corresponding problem.
It follows that every complexity that is expressed with big O notation is a complexity of the algorithm as well as of the corresponding problem.
It follows that every complexity that is expressed with big O notation is a complexity of the algorithm as well as of the corresponding problem.
用'''<font color="#ff8000">大O符号 big O notation</font>'''表示的每一个复杂度都是算法的复杂度，也是相应问题的复杂度。
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.
另一方面，问题复杂度的非平凡（nontrivial）下界一般难以获得，并且获得这种下界的方法很少。
For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least [[linear time|linear]], that is, using [[big omega notation]], a complexity <math>\Omega(n).</math>
For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least [[linear time|linear]], that is, using [[big omega notation]], a complexity <math>\Omega(n).</math>
The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of polynomial equations of degree in indeterminates may have up to <math>d^n</math> complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.
The solution of some problems, typically in computer algebra and computational algebraic geometry, may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a system of polynomial equations of degree in indeterminates may have up to <math>d^n</math> complex solutions, if the number of solutions is finite (this is Bézout's theorem). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.
一些问题的解可能是非常大的，特别是'''<font color="#ff8000">计算机代数 computer algebra</font>'''和'''<font color="#ff8000">计算代数几何 computational algebraic geometry</font>'''。在这种情况下，复杂度以输出的最大长度为下界，因此输出必须被写入。例如，如果解的个数是有限的，'''<font color="#ff8000">{{mvar|n}}个{{mvar|d}}次不确定多项式方程组 system of n polynomial equations of degree d in indeterminates </font>'''可能有多达 <math>d^n</math>个复解(这是'''<font color="#ff8000">贝佐定理 Bézout's theorem</font>''')。由于这些解必须被写入，所以这个问题的复杂度是<math>\Omega(d^n).</math>。对于这个问题，已知一个复杂度为<math>d^{O(n)}</math>的算法，因此可以认为是渐近拟最优的。