萨维奇定理
萨维奇定理（）是计算复杂性理论中的一个定理，由于1970年证明。定理的结论为对于任何函数f(n)满足f(n)\geq \log n，下列关系成立： :\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right). 亦即，如果一台非确定型图灵机能够利用f(n)空间解决某个问题，那么一台…
标签：#计算复杂性理论
共 9 篇文章
主定理
在演算法分析中，主定理（）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由喬恩·本特利、和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”（Master method）。此方法经由经典演算法教科书、、羅納德·李維斯特和的《算法导论》推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。 支配理论 假设有递归关系式 :T(n) = a \; T\!\left(\fr…
不可判定问题
不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 背景 决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题。因此，根据传统定义，寻求答案为是的输入值之集合的问题，与决定性问题等价。 与哥德尔不完备定理的关系 不可判定问题举例 参考资料
交互式证明系统
在计算复杂性理论中，交互式证明体系（以下简称交互证明）是一类计算模型。像其它计算模型一样，交互证明的目标是：对一个语言L，和一个给定的输入x，判断x是否在L中。交互证明由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。 交互证明的基本假设是：证明者在计算能力上…
算法分析
在计算机科学中，算法分析（）是分析执行一个给定算法需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分。 理论分析常常利用渐近分析估计一个算法的复杂度，并使用大O符号、大Ω符号和大Θ符号作为标记。举例，二分查找所需的执行步…
逻辑深度
逻辑深度（）是一种对事物复杂性的度量，由美国科学家于1988年提出。 事物的逻辑深度与其柯氏复杂度相关。柯氏复杂度也是一种对复杂性的度量，是指能够描述某一信息的最短程序的长度。而逻辑深度则是指运行该程序所需的时间步数，因而还与程序的计算复杂性有关。 参考文献
积和式
在线性代数中，积和式（）是一个由方块矩阵A计算得到的标量，记作\operatorname{perm}(A)。积和式的定义与行列式类似，只是在求和时不添加正负号。当矩阵A包含若干变量时，积和式也可以看作是一个关于这些变量的多项式。积和式在计算机科学，特别是计算复杂性理论中有重要的地位，因为理论上的一个重要难题——计算一个二分图（）上完美匹配（）的数目——等价于求某个矩阵的积和式。 定义 一个n \times n矩阵A=(a_{i,j})的…
函數問題
在计算复杂性理论内，函数问题（）或者功能性问题是一种，对任何一种输入都预期会有单一个输出，但是输出不像是决定性问题一样这么单纯。换句话说，输出不只是或否，比决策问题复杂得多。重要的范例像是旅行推销员问题，询问一张图是否有可以绕过每一点的不重复路径（输出为路径），以及整数分解，输出为输入的质因数。 因为没有明显类比的语言，函数问题比起决定型问题要难以研究。而且因为输出的可能变多，在解决输入输出之间的转换，函数问题归约的过程也比较微妙。函数…
伪多项式时间
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。 一个具有伪多项式时间复杂度的NP完全问题称之为，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为。 例子 在素性测试}-中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数…