学科分类 - 《中国大百科全书》第三版网络版

高级搜索

个人中心
机构中心
退出

专业板块专题板块大众板块

总分类

哲学经济学法学教育学文学历史学理学工学农学医学军事学管理学艺术学

返回总分类

首页

计算复杂性/ computational complexity // computational complexity /

研究一个计算问题所需要的计算资源的数量。计算资源有很多，其中最常用的是时间与空间，分别对应于时间复杂性和空间复杂性。两者的基本定义思路是一致的，本条目中以最常用的时间复杂度为例，也就是研究一个计算问题所需的运行时间。

PCP定理/ probabilistically checkable proofs theorem,PCP theorem /probabilistically checkable proofs theorem,PCP theorem
计算复杂性
PCP是在交互式证明系统的基础上，通过增加一条随机带，使之具有带随机存储和神谕功能的概率可验证证明系统。PCP定理基于概率可验证计算模型给出了NP类语言（见非确定多项式时间NP类）的一种新的表示（特征）：一个语言是NP语言，当且仅当它的元素的成员资格验证具有多项式长度的证明，并且其正确性只需随机检查常数次位信息。
电路复杂性/ circuit complexity /circuit complexity
计算复杂性
电路复杂性（circuit complexity）是计算复杂性的研究方向之一。电路（circuit）是与图灵机不同的一种计算模型。电路由门（gate）和导线（wire）组成，门与门之间通过导线连接。电路的规模（size）是电路的门数或导线数，电路的深度（depth）是从输入到输出的最长路径的长度。电路复杂性通常是指电路的规模或深度。一个计算问题的电路复杂性是计算此问题的电路的最小规模或深度。电路复杂性的下界证明是难度很大、富有挑战性的研究方向。
通信复杂性/ communication complexity /communication complexity
计算复杂性
计算复杂性的研究方向之一。其只考虑多方（通常是两方）合作计算过程中通信的开销，而忽略各方本地计算的开销。作为一个基础模型，它在很多领域的各种下界（lower bound）证明中起着重要作用。
描述复杂性/ descriptive complexity /descriptive complexity
计算复杂性
在图灵机上产生一个给定输出所需要的最短输入的长度。又称柯尔莫哥洛夫复杂性。
交互式证明/ interactive proof /interactive proof
计算复杂性
包含了非确定性（nondeterminism）、随机性（randomness）、交互性（interaction）的一种计算模型。一个交互式证明系统由证明器（prover）和验证器（verifier）组成。证明器的计算能力无限（非确定性），验证器的计算能力有限但可以利用随机数（随机性）、证明器和验证器之间交替地发送消息（交互性）。
证明复杂性/ proof complexity /proof complexity
计算复杂性
关注逻辑系统中命题的最短证明的长度的计算复杂性的研究方向之一。
判定树复杂性/ decision tree complexity /decision tree complexity
计算复杂性
判定树（decision tree）是一种简单的算法模型，它的基本运算是查询输入的某一位，并根据查询结果决定下一个查询位，直到计算出结果为止。判定树复杂性（decision tree complexity），就是在长度为n的输入上用判定树计算一个函数所需要查询的最多位数，通常是n的函数，最大值不超过n。又称查询复杂性（query complexity）。
计数复杂性/ counting complexity /counting complexity
计算复杂性
计数问题的算法易解性和计算困难性（见计算复杂性）。
复杂性类/ complexity class /complexity class
复杂性类
复杂性类是计算模型在资源约束下能够求解的问题类，计算模型有图灵机和电路等，资源有时间、空间、随机性、交互性、非确定性等。常见的复杂性类有时间复杂性类、空间复杂性类、概率复杂性类、量子复杂性类、电路复杂性类（见电路复杂性）、交互式证明系统（见交互式证明）等。复杂性类可以是判定问题类，也可以是函数类。
多项式谱系PH/ polynomial hierarchy; PH /polynomial hierarchy; PH
时间复杂性类
对非确定多项式时间NP类的推广。

计算复杂性/ computational complexity // computational complexity /

PCP定理/ probabilistically checkable proofs theorem,PCP theorem /probabilistically checkable proofs theorem,PCP theorem

电路复杂性/ circuit complexity /circuit complexity

通信复杂性/ communication complexity /communication complexity

描述复杂性/ descriptive complexity /descriptive complexity

交互式证明/ interactive proof /interactive proof

证明复杂性/ proof complexity /proof complexity

判定树复杂性/ decision tree complexity /decision tree complexity

计数复杂性/ counting complexity /counting complexity

复杂性类/ complexity class /complexity class

多项式谱系PH/ polynomial hierarchy; PH /polynomial hierarchy; PH