【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《计算理论定理定义总结》，欢迎阅读！
定义1.1：有穷自动机是一个 5 元组 ( Q, , , q0, 定理4.6：ACFG是一个可判定语言。 在任何长度为n的输入上所所有有的计算分支中最大步数。 F )，其中(1) Q 是一个有穷集合，称为状态集。(2) 是定理4.7：ECFG是一个可判定语言。 定理7.10：设 t(n)是一个函数， t(n) ≣ n 。则每一个 t(n) 时O(t(n))一个有穷集合，称为字母表。(3) : QQ是转移函定理4.8：每个上下文无关语言都是可判定的。 间的非确定型单带图灵机都与某一 2时间的确定型图灵机等数。(4) q0Q 是起始状态。(5) FQ 是接受状态集。 定理4.9：ATM 是不可判定的。 价。
定义1.7：如果一个语言被一台有穷自动机识别，则称定义4.10：设 A 和 B 是两个集合，f 是从 A 到 B 的函数。如定义7.11：P是确定型单带图灵机在多项式时间内可判定的语言k它是正则语言。 果 f从不将 两个不同元素映射到同一个对象，即：只要a ≠b 就类。换言之， P＝∪TIME(n)。 DFA和NFA的区别：1、DFA每个状态对于字母表中的每有 f (a)≠f (b)，则称 f 是一对一映射的。如果 f 能击中 B 的1．对于所有与确定型单带图灵机多项式等价的计算模型来说，P个符号总是恰好有一个转移箭头射出。NFA一个状态对每个元素，即：对 B 的每个元素b，都存在 a A，使得 f (a) =b，是不变的。2. P大致对应于在计算机上实际可解的那一类问题。 于字母表中的每一个符号可能有0个1个或多个射出的则称 f 是满映射。如果存在函数 f：A B，f 是一对一映射又定理7.12：PATH∈P
箭头；2、在DFA中，转移箭头上的标号是取自字母表的是满映射，则称集合 A 和 B 有相同规模。而既是一对一映射又定理7.13：RELPRIME∈P 符号。而NFA的箭头可以标记字母表中的符号或。 是满映射的函数称为对应。在对应中，A 的每个元素映射到 B 的定理7.14：每一个上下文无关语言都是P的成员。 定义1.17：非确定型有穷自动机 (NFA) 是一个 5 元组 唯一一个元素，且 B 的每个元素都有A的唯一一个元素映射到它。定义7.16：NP是具有多项式时间验证机的语言类。NP即非确定( Q, , , q0, F )，其中(1) Q 是有穷的状态集。(2) 对应就是将 A 的元素与 B 的元素进行配对的方法。 型多项式时间
是有穷的字母表。(3) : QεP(Q)是转移函数。定义4.12：如果一个集合 A 是有限的或者与 N 有相同的规模，定理7.17：一个语言在NP中，当且仅当它能被某个非确定型多(4) q0Q 是起始状态。(5) FQ 是接受状态集。 则 A 是可数的。 项式时间图灵机判定。 正则表达式的形式化定义：称 R 是一个正则表达式，如推论4.15：存在不能被任何图灵可识别的语言。 定义7.18：NTIME(t(n)) = {L| L是一个被O (t(n))时间的非确定型果 R 是(1) a，这里 a 是字母表 中的一个元素；(2) 定理4.16：一个语言是可判定的，当且仅当它既是图灵可识别的，图灵机判定的语言} ；(3) 也是补图灵可识别的。 推论7.19：NP = ∪kNTIME(nk) (4) R1∪R2，这里 R1 和 R2 是正则表达式；(5) R1R2 ，可以证明：如果一个语言和它的补都是图灵可识别的，则此语言定理7.20：CLIQUE属于NP 这里 R1 和 R2 是正则表达式；(6) R1* ，这里 R1 是也是可判定的。 定理7.21：SUBSET-SUM属于NP 正则表达式； 这样，对任何不可判定语言，它或它的补至少有一个不是图灵可定理7.22：库克-列文（Cook-Levin）定理：SAT∈P，当且仅当定义1.33：GNFA M = (Q, , , qstart, qaccept)（1）识别的。 P=NP。 Q 是有穷的状态集。(2) 是输入字母表。(3) 一个语言的补是由不在此语言中的所有串构成的语言。 定义7.23：若存存在在多项式时间图灵机M，使得在任何输入w:(Q-{qaccept}(Q-{qstart} R 是转移函数。 (4) 如果一个语言是一个图灵可识别语言的补集，则称它是补图灵可上，M停机时f(w)恰好在带上，称函数f：Σ*→ Σ*为多项式时qstart 是起始状态。(5) qaccept 是接受状态。其中 R 识别的。 间可计算函数。 是正则表达式。 推论4.17：Ā TM 不是图灵可识别的。 定义7.24：语言A称为多项式时间映射可归约到语言B，或简称定理1.37（泵引理）：若 A 是一个正则语言，则存在一定理5.1：HALTTM是不可判定的。 多多项项式式时时间间可可归归约约到B，记为A≢pB，若存在个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小定理5.2：ETM 是不可判定的。 多项式时间可计算函数 f：Σ* → Σ*，对于每一个w，有w∈A f(w)于 p 的字符串，那么 s 可以被分成 3 段，s = xyz，定理5.3：REGULARTM是不可判定的。 ∈B，函数f 称为A到B的多多项项式式时时间间归归约约。 满足下述条件：(1) 对于每一个 i 0, xyiz∈A ；(2) 定理5.4：EQTM是不可判定的。 定理7.25：若 A≢pB 且 B∈P，则 A ∈P。 | y | 0；(3) | xy | ≢ p 定义5.5：设M是一个图灵机，w是一个串。M在w上的一个接受定理7.26：3SAT多项式时间可归约到CLIQUE 上下文无关文法：(1) 写下起始变元——第一条规则左计算历史是一个格局序列C1，C2，．．．,Cl，其中C1是M在w上的定义7.27：如果语言B满足下面两个条件，就称为NP完全的：1）边的变元。(2) 取一个已写下的变元，并找到以该变元起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法B 属于NP，并且2）NP中的每个A 都多项式时间可归约到 B 开始的规则，把这个变元替换成规则右边的字符串。(3) 结果，即符合M的规则。M在w上的一拒绝计算历史可类似定义，定理7.28：若上述的 B 是NP完全的，且B ∈P，则P=NP。 重复步骤2，直到写下的字符串没有变元。 只是Cl应是一个拒绝格局。 定理7.29：若上述的 B 是 NP 完全的，且B ≢pC，C 属于NP，定义2.1：上下文无关文法是一个 4 元组 ( V, , R, 定义5.6：线性界限自动机是一种受到限制的图灵机，它不允许其则 C 是 NP 完完全全的的。 S )，且(1) V 是一个有穷集合，称为变元集；(2) 是读写头离开包含输入的带区域。如果此机器试图将它的读写头移定理7.30：SAT 是NP完全的 一个与 V 不相交的有穷集合，称为终结符集；(3) R 是出输入的两个端点，则读写头就保持在原地不动。这与普通图灵断言7.31：如果表的顶行是起始格局，表中的每一个窗口都是合一个有穷规则集，每条规则由一个变元和一个由变元及机的读写头不会离开带子的左端点的方式一样。 法的，那么表的每一行都是从上一行合法转移得到的格局。 终结符组成的字符串构成；(4) SV 是起始变元。 引理5.7：设M是有q个状态和g个带符号的LBA。对于长度为 n推论7.32：3SAT 是NP完全的，CLIQUE 是NP完全的，VERTEX 如果 u = v ，或者存在 u1, u2, …, uk, k 0 使得的带子，M恰有qngn个不同的格局。 - COVER是NP完全的，HAMPATH 是NP完全的 u u1 u2… uk v，则称 u 派生 v，记作 u * 定理5.8：ALBA是可判定的。 定理7.36：UHAMPATH 是NP完全的，SUBSET-SUM 是NP完v。 定理5.9：ELBA是不可判定的 全的 最左派生：对于文法 G 中的一个字符串 w 的派生，如定理5.10：ALLCFG是不可判定的。 定义8.1：令M是一个在所有输入上都停机的确定型图灵机。M果在每一步都是替换左边剩下的变元，则称这个派生是定义5.12：函数f： * * 是一个可计算函数，如果有图灵机的空间复杂度是一个函数f：N →N，其中f(n)是M在任何长为n最左派生。 M，使得在每个输入w上 停机，且此时只有f(w)出现在带上。 的输入上扫描带方格的最大数。若M的空间复杂度为f(n)，也称定义2.4：如果字符串 w 在上下文无关文法 G 中有两定义5.15：语言A是映射可归约到语言B的，如果存在可计算函M在空间f(n)内运行。
个或两个以上不同的最左派生，则称 G 歧义地数 f： **使得对每个w，w∈A等价于f(w) ∈B记作A≢mB。定义8.2：令f：N → R+是一个函数，空间复杂性类SPACE(f(n))(ambiguously) 产生字符串 w，如果文法 G 歧义地产生称函数f为A到B的归约。 和NSPACE(f(n))定义如下：SPACE(f(n))={L|L是被O(f(n))空间的某个字符串，则称 G 是歧义的。某些上下文无关语言只定理5.16：如果A≢mB且B是可判定的，则A也是可判定的。 确定型图灵机判定的语言}NSPACE(f(n))={L|L是被O(f(n))空间的能用歧义文法产生，这样的语言是固有二义的。 推论5.17：如果A≢mB且A是不可判定的，则B也是不可判定的。 非确定型图灵机判定的语言}
定义2.5：称一个上下文无关文法是为乔姆斯基范式定理5.22：如果A≢mB，且B是可图灵可识别的，则A也是图灵定理8.5：萨维奇定理：对于任何函数f：N → R+，其中f(n) ≣ (Chomsky normal form)，如果它的每一个规则具有如下可识别的。 n，NSPACE(f(n)) SPACE(f2 (n)) 形式：A BC A a其中 a 是任意的终结符，A、B 和 推论5.23：如果A≢mB，且A不是图灵可识别的，则B也不是图定义8.6：PSPACE是在确定型图灵机上、在多项式空间内可判定C 是任意的变元，且 B 和 C 不能同时是起始变元。此灵可识别的。 的语言类。换言之，PSPACE＝∪SPACE(nk) 外，允许规则S ，其中 S 是起始变元。 定理5.24：EQTM既不是图灵可识别的，也不是补图灵可识别的。 定义8.7：语言B是PSPACE完完全全的的。若它满足下面两个条定理2.6：任一上下文无关语言都可以用一个乔姆斯基引理6.1：存在可计算函数 q: * * ，对任意串w, q(w)是件：1) B属于PSPACE。2) PSPACE中的每一个语言A多项式时间范式的上下文无关文法产生。 图灵机Pw的描述，Pw打印出w，然后停机。 可规约到B 。若B只满足条件2，则称它为PSPACE难的。 定义2.8：PDA是一个6元组M=(Q,Σ,Γ,δ, q0, F)，SELF的构造：（1）A部分首先运行，再根据完成情况将控制传给B。定理8.8：TQBF是PSPACE完全的，FARMULA-GAME是PSPACE其中(1)Q——状态的有限集合。(2)Σ——输入字母表。A的任务是打印出B的描述。B的任务是打印出A的描述。（2）先完全的 (3)Γ——栈字母表。(4)δ：状态转移函数，Q×Σε ×构造A部分（3）使用机器P来定义A，其中P用函数q在P 包含NP包含PSPACE=NPSPACE包含EXPTIME Γε P（ Q×Γε ） 。(5)q0——q0∈Q，开始状态。 处的值q()描述，这样，A部分是一个打印出的图灵机。AL包含NL = coNL包含P包含PSPACE (6)F——FQ，终止状态集合。 的描述依赖于是否已经有了B的描述，所以在构造出B之前，无定理9.3：空间层次定理。对于任何空间可构造函数f:N→N，存定理2.12：一个语言是上下文无关的，当且仅当存在一法完成A的描述。（4）对于B部分：从A产生的输出来计算A（5）在语言A，在空间O(f(n))内可判定，但不能在空间o(f (n))内可判台下推自动机识别它。 如果B能够得到，就能应用q来得到。但B如何得到？定。
引理2.13：如果一个语言是上下文无关的，则存在一台当A结束时，它被留在带上。所以B只要看着带子就能得到。定理9.10：时间层次定理。对于构造函数t: N→N，存在语言A，下推自动机识别它。 计算q()=之后，B将之加到带的前面。然后将A和B组合在时间O(t(n))内可判定，但在时间o(t(n))/logt(n)内不可判定。 引理2.15：如果一个语言被一台下推自动机识别，则它成一个机器并在带上写下它的描述= 。 定义9.16：针对一个语言A的谕示是一个能够判断任何串w是否是上下文无关的。 定理6.2：（递归定理）设T是计算函数 t: * × * * 的在该语言中的设备。谕示图灵机MA就是给通常的图灵机附加一条断言2.16：如果Apq产生x，则x能够把P从p和空栈一一个图灵机。则存在计算函数r: * * 的一个图灵机R，使带子，称为谕示带。每当MA在谕示带上写下一个字符串时，它就块带到q和空栈。 得对每一个w，有：r(w) = t(, w) 能在一步计算内得知这个字符串是否属于A。
断言2.17：如果x能够把P从p和空栈带到q和空栈，定义6.4：如果M是一个图灵机，则M的描述 的长度是描述定理9.19：1)存在谕示A使得PA≠NPA。2)存在谕示B使得PB＝则Apq产生x。 M的串中所含符号的个数。如果没有与M等价的图灵机有更短的描NPB。 定理2.19：如果A是上下文无关语言，则存在数p（泵述，则称M是极小的。令MINTM＝{| M是一个极小TM} 定理10.1：上述算法A是一个多项式时间算法，它给出G的一个长度），使得A中任何一个长度不小于p的字符串s都能定理6.5：MINTM不是图灵可识别的。 顶点覆盖，其规模不超过G的最小顶点覆盖的2倍 被划分为5段s = uvxyz且满足下述条件：1. 对于每一定理6.6：设 t: * * 是一个可计算函数，则存在一个图灵定理10.2：上述算法B是MAX-CUT的2-优的多项式时间近似算个i 0, uvixyiz ∈A；2. |vy| 0；3. |vxy| p。 机F，使得t()描述一个与F等价的图灵机。这里假设如果串法 定义3.1：TM是一个7元组(Q, , , , q0, qAcc, 不是一个正确的图灵机编码，那么它描述的图灵机立即拒绝。 定义10.3：BPP是多项式时间的概率图灵机以错误概率1/3识别qRej) ，其中：（1）Q ： 状态集（2） ： 输入字母表, 定义6.20：设x是二进制数的串，x的极小描述，记为d(x)，是的语言类。
不包括空白字符（3） ： 带字母表, and 最短的串，w>，其中：TM M在输入w上停机时，x在带上。且引理10.5：设ε是一给定的常数，且0<ε<1/2。又设M1是一台 （4） ： 转移函数 : Q x Q x x { L, R }, 如果有多个这样的串存在，则在其中选择字典序下的第一个串。x错误概率为ε的多项式时间概率图灵机，则对于任意给定的多项式（5）q0：开始状态（6）qAcc： 接受状态,（7） qRej：的描述复杂性记为K(x)，是K(x) = |d(x)|换句话说，K(x)是xpoly(n)，存在与M1等价的错误概率为2-poly(n)的多项式时间概率拒绝状态。 的极小描述的长度。K(x)的定义是为了刻画串x中的信息量这个图灵机M2。 格局：当前状态q Q 当前带内容 * 读写头位置 直观概念的。 定理10.6：（费马小定理）如果p是素数，且a∈Zp+，则ap-1≡1 (modp) {0,1,2,…} 定理6.25：设x是一个串，如果k（x）≢|x|-c，则称x是c可引理10.7：如果p是一个奇奇素素数数，则Pr[ PRIME接受p ] = 1 定义3.2：如果一个语言能被某一图灵机识别，则称该压缩的(c-compressible)。如果x不是c可压缩的，则称x是不引理10.8：如果p是一个奇合数，则Pr[ PRIME接受p ]≢2-k 语言是图灵可识别的。 可压缩c的。如果x是不可压缩1的则称x是不可压缩的。 定理10.9：PRIMES ∈ BPP 定义3.3：如果一个语言能被某一图灵机判定，则称它定理6.26：对于每个长度，都存在不可压缩的串。 定义10.10：RP是多项式时间概率图灵机识别的语言类，在这里，是图灵可判定的。 推论6.27：至少有2n - 2n-c+1 + 1个长度为n的串是不可压缩在语言中的输入以不小于1/2的概率被接受；不在语言中的输入以定理3.8：每个多带图灵机等价于某一个单带图灵机 c的。 概率1被拒绝。
推论3.9：一个语言是图灵可识别的，当且仅当存在多定理6.28：设f是一个对几乎所有串成立的性质，则对任意b>0，定义10.11：分支程序是一个有向无环图。其中，除两个输出顶点带图灵机识别它。 性质f只在有限多个不可压缩b的串上的值是FALSE。 标记为0或l外，它的所有顶点都被标记为变量。被标记为变量的定理3.10：每个非确定型图灵机等价于某一个确定图灵定理6.29：存在常量b，使得对每个串x，x的极小描述d(x)都是顶点叫做查询顶点。每一个查询顶点引出两条边，一条标记0、另机 不可压缩b的。 一条标记1。两个输出顶点没有引出的边。在分支程序中指定一个推论3.11：一个语言是图灵可识别的，当且仅当存在非定义7.1：令M是一个在所有输入上都停机的确定型图灵机。M的顶点为起始顶点。 确定性图灵机识别它。 运行时间或者时间复杂度，是一个函数f：N →N，其中N是非非定理10.12：EQROBP在BPP中
推论3.12：一个语言是可判定的，当且仅当存在非确定负负整整数数集合， f(n)是M在所有长度为n的输入上运行时所引理10.13：对于每一个d≧0，单变量x的d次多项式p或者最性图灵机判定它。 经过的最大步数。若f(n)是M的运行时间，则称M在时间f(n)内多有d个根，或者处处等于0。 定理3.13：一个语言是图灵可识别的，当且仅当有枚举运行，M是f(n)时间图灵机。通常使用n表示输入的长度。 引理10.14：设F是f个元素的有限域，p是x1,…,xm的不恒为0器枚举 定义7.2：设f 和g 是两个函数f ，g： N → R+。称f(n)=O(g(n))，的多项试，每一个变量的次数不超过d。如果a1,… ,am随机地选图灵机描述：形式化描述：详尽地写出图灵机的状态、若存在正整数c和n0，使得对所有n ≣n0有f(n) ≢ cg(n)当取自F，则Pr[p(a1,…,am)=0] ≢ md/f。
转移函数等，属于最低层次、最详细程度的描述；实现f(n)=O(g(n))时，称g(n)是 f(n)的上界，或更准确地说， g(n)定义10.15：交错式图灵机（alternating Turing machine）是一种具描述：使用日常语言描述图灵机动作，如怎么移动读写是 f(n)的渐近上界，以强调没有考虑常数因子。 有特殊功能的非确定型图灵机。除qaccept和qreject外，它的状态头、怎么在带上存储数据等，这种程度的描述没有给出大O记法指一个函数渐渐近近地地不不大大于于另一个函数。小o分成全称状态（universal state）和存在状态（existential state）。当状态和转移函数的细节；高水平描述：也使用日常语言记法是渐进的小于另一个函数。大O记法与小o记法的区别类似对输入串运行交错式图灵机时，根据对应的格局是包含全称状态还来描述算法，但忽略了实现的模型，不需要提及机器怎于≢和＜之间的区别。 是包含存在状态，用∧或∨标记它的非确定型计算树的每一个顶样管理它的带子或读写头。 定义7.7：令t：N → R+是一个函数。定义时间复杂性类TIME(t(n))点。如果一个顶点标记∧且它的儿子都接受，或者标记∨且它的儿定理4.1：ADFA是一个可判定语言。 为由O(t(n))时间的图灵机判定的所有语言的集合。 子中有一个接受，则规定这个顶点接受。 定理4.2：ANFA是一个可判定语言。 定理7.8：设t(n)是一个函数， t(n) ≣n。则每一个时间t(n)定理10.19：对于f(n) ≣n，有ATIME(f(n))包含SPACE(f(n))包含定理4.3：AREX 是一个可判定语言。 的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价。 ATIME(f2(n))对于f(n) ≣logn，有ASPACE(f(n)) = TIME(2O(f(n)))因定理4.4：EDFA 是一个可判定语言。 定义7.9：设N是一个非非确确定定型型图图灵灵机机，并且是一此，AL=P、AP=PSPACE以及APSPACE =EXPTIME。 定理4.5：EQDFA是一个可判定语言。 个判判定定机机。N的运行时间是函数f：N → N ，其中f(n)是
本文来源：https://www.wddqxz.cn/f03430ec0ba1284ac850ad02de80d4d8d05a015e.html
2023-04-22
