307
个编辑
更改
跳到导航
跳到搜索
第135行：
第135行： + 第140行：
第141行： − 复杂性的评估依赖于计算模型的选择，其中包括定义在一个时间单位内完成的基本操作。当计算模型没有被明确指定时，这通常被认为是多带图灵机。+ + 第150行：
第152行： − 一个确定性模型的计算是这样一种计算模型，即机器的连续状态和要执行的操作完全由前面的状态决定。历史上，第一个确定性模型是递归函数、 lambda 演算和图灵机。随机存取机器(也称 RAM-machines)的模型也被广泛使用，作为更接近真实计算机的对应物。+ 第223行：
第225行： − −
→Models of computation
==Models of computation==
==Models of computation==
计算模型
The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being [[multitape Turing machine]].
The evaluation of the complexity relies on the choice of a [[model of computation]], which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being [[multitape Turing machine]].
The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being multitape Turing machine.
The evaluation of the complexity relies on the choice of a model of computation, which consists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, this is generally meant as being multitape Turing machine.
复杂度的评估依赖于'''<font color="#ff8000">计算模型 model of computation</font>'''的选择，包括定义在一个时间单位内完成的基本操作。当计算模型没有被明确指定时，它通常被认为是'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。
===Deterministic models===
===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.
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 functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.
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 functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.
一个'''<font color="#ff8000">确定性模型 deterministic model </font>'''的计算是一种机器的连续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，第一个确定性模型是'''<font color="#ff8000">递归函数 recursive functions</font>'''、 '''<font color="#ff8000">lambda 演算 lambda calculus</font>'''和'''<font color="#ff8000">图灵机 Turing machines</font>'''。'''<font color="#ff8000">随机存取机器 Random access machine </font>'''(也称 RAM-machines)的模型也被广泛使用，作为更接近真实'''<font color="#ff8000">计算机 computer</font>'''的对应物。
量子复杂性理论已经发展到研究用量子计算机解决的问题的复杂性类。它用于后量子密码学，其中包括设计抗量子计算机攻击的密码协议。
量子复杂性理论已经发展到研究用量子计算机解决的问题的复杂性类。它用于后量子密码学，其中包括设计抗量子计算机攻击的密码协议。
==Problem complexity (lower bounds)==
==Problem complexity (lower bounds)==