计算复杂性理论部分进展简述1
https://www.wendangku.net/doc/473474377.html, 计算复杂性理论部分进展简述
蔡进一葛启朱洪
前言
计算复杂性理论博大精深，它在整个计算机科学领域处于核心的地位（此句程虎老师认为过头，建议改为地位之一）。复杂性理论和算法的不同之处在于，它不是单单研究解决某个问题的方法，而是研究一类问题的性质。在上世纪60年代中期，Hartmanis等人提出了通过对资源（时间、空间）需求的不同来划分问题，从此开创了计算复杂性理论。此后几年，大量复杂性类被提出，并且很多新方法被应用，计算复杂性的框架被建立起来。但是随着研究的深入，越来越多的问题也涌现出来，比如说经典的问题P =?NP，是计算复杂性中的核心问题。随着新的问题以及新模型的提出，计算复杂性理论被不断地丰富，并且每一次重大成果的出现都必然伴随着新方法的使用。
本文在第二部分介绍了近20年来，复杂性理论最重要的成果之一，即交互证明系统模型，以及它对证明NP 难问题不可近似性的贡献。这一部分主要按时间的顺序，介绍了交互证明系统的发展过程，其间的重要结论，所使用的主要方法，以及如何通过交互证明系统来求NP难问题的不可近似度。
本文在第四部分介绍了计算复杂性理论一个最新进展，即对数空间复杂性类之间的关系，这些复杂性类的提出由来已久，但是直到2005年才有了突破性的结果。在这一部分将介绍这些复杂性类的来源，这个突破性的结果以及所使用的方法。
交互证明系统以及不可近似性
交互证明系统的提出及发展
在数学中，为了证明一个命题，其方法都是罗列出一串过程，或者说是证据，然后利用最基本的公理的正确性以及证据之间的逻辑关系，最终得到命题的正确性。其实简化一些来看，这个过程就是证明者为了证明某个命题的正确性，从而将一些证据都列举出来，他认为从这些证据可以得出命题的正确性。而对其他人（称作验证者）来说，如果要检验证明者的结果，只要将其证明的过程验证一遍，按照其证据之间的关系以及某些公理假设，看是否可以最终得到其所提出的命题的正确性，如果可以，就认为这个命题是正确的，否则为假。这个过程可以简单地看作一个一轮的交互过程或者证据，即证明者将他的证明过程发送给验证者，然后由验证者验证。
而交互证明系统IP（Interactive Proof Systems）正是将以上的数学证明方法推广的一个模型。交互证明系统由两方组成，一方称为证明者（Prover），一方为验证者（Verifier）。对于给出的某个命题，证明者总是要说服验证者命题的正确性（不管这个命题本身是否真的正确），证
1Supported by NSF Grant, USA (CCR-0208013) and NSFC Grant, 60496321
https://www.wendangku.net/doc/473474377.html,
者在得到这些证据后验证其正确性，同时，验证者可能还会有疑问，他可以向证明者提出问题，证明者需要回答这些问题。并且双方在交互中都可以使用随机串，即验证者可能有很多问题需要证明者来回答，但是他没有办法等待这么多时间来验证所有问题的答案，所以他会采用随机的方法，从中选取一些题目要求证明者回答。在进行完所有的交互以后，验证者判断证明者给出的证明过程是否足以证明命题的正确性。
交互证明系统最初由Goldwasser、Micali和Rackoff[27]以及Babai [5]分别提出。
定义1（Goldwasser et al. [27]）一个语言L的交互证明系统是一个由证明者和验证者组成的交互过程，他们有共同的输入，并且他们的交互过程满足如下的条件：
1.验证者的策略是一个概率多项式时间的过程。
2.证明者的计算能力没有限制。
3.正确性要求：
●完备性：存在一个证明策略P，对于任意的x 2 L，当交互的输入为x时，证明者P 可以以至少2/3的概率使得验证者接受。
●可靠性：对于任意的x 62 L，当交互的输入为x时，对于证明者的任意的策略P*，至多只能以1/3的概率使得验证者接受。
Babai所的定义的交互证明系统被称为Arthur-Merlin Games。它与交互证明系统不同之处在于：它的验证者Arthur被要求只能给证明者Merlin随机串，而不能是由验证者计算出来的信息。这种系统又被称作Public-Coin Systems。
虽然在形式上有所不同，但在1986年由Goldwasser和Sipser[29]证明了这两种系统在计算能力上是等价的。
定义2（Goldwasser and Sipser [29]）如果一个语言L 存在Q 轮的交互证明系统，那么存在Q+ 2轮的Arthur-Merlin Game判定这个语言，即IP[Q] μ AM[Q + 2]。
在这个证明过程中，成功地应用了一种称为Universal Hash Functions的方法。它起始于Carter和Wegman的[15]，后来被广泛的应用于随机复杂性类的分析中，比如BPP μΣ2的证明，#P 类的近似计数（参考[50, 54]），以及伪随机函数的设计、退随机等等。
在复杂性理论的研究中，一个新的复杂类的提出，或是为了更好地分析现有的复杂类之间的关系，或是为了考察某些实际的问题，但最后都会研究这个复杂类在现有框架下的位置。交互证明系统的提出，是为了找到一个既包含NP语言又包含BPP语言的复杂性类（对于基本的复杂性类的定义，可以参考经典的复杂性文献，如[34, 44, 49, 17]等）。交互证明系统是一种能力很强的模型。在1990年由Shamir[48]证明了IP = PSPACE。
在Shamir的文章中，使用了两种重要的技术，这两种技术对于后面PCP系统的性质的证明起到了关键的作用。第一个技术称作低阶多项式（low-degree polynomial）技术。它主要是基于多项式的一个简单的性质：一个阶数不超过d的多项式，其根的数目不会超过d；或者描述为：两个阶数不超过d 的多项式，如果它们在超过d 个不同的点上值相等，那么这两个多项式相等。如果选取一个较大的质数p〉〉d，使得多项式定义在Z p上，现在随机选取一个点a 2 Z p，那么这两个多项式在点a上相等的概率就会非常小，通过这种方法可以减少证明者对验证者的欺骗。
另一种技术称为代数化方法。通过这种方法，可以将一个布尔表达式或者带量词约束的布尔表达式转化为多项式。它将一个布尔变量x i对应到一个取值为正整数的变量x i，将一个变量的补x i转化为1－x i，将∨用狄摩更律转化为∧，而∧表示为相应文字的乘积。这样就可以通过验证多项式值的问题来检测布尔表达式的可满足问题。
多证明者的交互证明系统及PCP系统
在交互证明系统中，验证者只有依靠使用随机串的方法来防止证明者的“欺骗”，但是，
https://www.wendangku.net/doc/473474377.html,
的，也就是说，可能这些语言不存在交互证明系统。在1988年，Ben-Or、Goldwasser、Kilian 和Wigderson[10]引入了新的验证模型，称为多证明者的交互验证系统（multi-prover interactive proof）。在这个系统中，证明者由一个变为多个，并且这些证明者之间不能进行交流，从而使得证明者不能“轻易”地欺骗验证者，因为验证者可以通过向其他证明者询问同样的问题而得到矛盾的结果。
接下来的问题就是对于多证明者的交互证明系统，它的计算能力有多强。如果用MIP k来表示k个证明者的多证明者交互系统所能判定的语言，很明显IP μ MIP2 μ MIP3 μ…μ MIP，即这个系统够成了一个分层（hierarchy）。但是在[10]中，证明了MIP = MIP2，也就是说，只需要两个证明者就够了，其他都是多余的。在同一年，Fortnow、Rompel和Sipser[24]证明了MIP μNEXPTIME。其后，Babai、Fortnow和Lund[7]又证明了MIP = NEXPTIME。在这个证明中，所使用的方法仍然是代数化和低阶多项式技术。
由于有了MIP = NEXPTIME 这样的结论，自然而然会联想到NP，因为NP和NEXPTIME 的不同之处在于其所需要的计算时间，所以就提出一个问题，是否可以通过限制多证明者交互系统的某些参数，比如说交互的轮数或者随机串的数目来得到与NP类相等价的复杂性类。
在[24]中提出了一个与在计算能力上等价的模型，这种模型在后来Arora和Safra[4]的文章中被称为概率验证模型（probabilistically checkable proofs）。
定义3（Fortnow et al.[24]）若M是一个多项式时间概率图灵机并且可以访问神谕（oracle）带O。M接受语言L当且仅当：
1. 存在一个神谕带O，对于任意的x 2 L都有M O以大于1—2?n的概率接受x。
2. 对任意的x 62 L，对所有的神谕带O’，M O’接受x的概率都小于2-n。
可以看到，与多证明者交互证明系统的不同之处在于，概率验证系统中神谕带是“无记忆的”，也就是如果确定了神谕带以后，对验证者问题的回答都是确定的，而不像在交互证明系统中，证明者可以根据以前的回答来调整当前的回答，以达到欺骗验证者的目的。但是，Fortnow、Rompel和Sipser在[24]中，证明了多证明者交互证明系统与概率验证系统的能力是一样的，也就是MIP = PCP。
在交互证明系统中，有两个参数是比较重要的，一个就是验证者使用的随机串的长度，一个是验证者从神谕带上获得信息的长度。这些参数直接影响到概率验证系统的计算能力。在前面的定义中，因为图灵机的时间限制在多项式时间内，所以其使用的随机串和访问的神谕带位数都是多项式的，也就是MIP = PCP(O(poly(n)),O(poly(n)))。在其后的几年中，围绕这两个参数进行了一系列的研究，主要目的就是缩小这两个参数的值，从而更紧致地刻画NP类。
在[6]这篇文章中，证明了NP μ PCP(O(polylog(n)),O(polylog(n)))。其后Feige、Goldwasser、Lovasz、Safra和Szegedy[22]证明了
NP μ PCP(O(log(n)loglog(n));O(log(n)loglog(n)))。
这篇文章给出的从PCP系统到团问题的归约的思想，后来被广泛用于不可近似性的证明。在1992年，Arora和Safra[4]加强了以上的结果，证明了NP μ PCP(O(log(n)),O(log(n)))。此时因为所用到的随机串为对数大小，所以所有可能的随机串为多项式，又因为访问的位数为对数长度，从而整个神谕带的长度为多项式，进而可以得到NP = PCP(O(log(n)),O(log(n)))。随后，这个结果又被加强：Arora、Lund、Motwani、Sudan和Szegedy[3]证明了NP = PCP(O(log(n)),O(1))，也就是只需使用对数长度的随机串，并且访问常数位的神谕带就可以验证一个输入。这个定理被称为PCP定理。
这个结论的得出，使得NP可以使用另一种新的模型来刻画，这种模型在x 2 L和x 62 L的接受概率中存在很大的间隙（可以参考定义3中的两个不同的概率)，这个间隙也是后面刻画NP难问题不可近似性的基础。
https://www.wendangku.net/doc/473474377.html,
在第一个NP-complete判定问题被证明以前，对应的NP-极值（优化）问题的近似算法的概念就已经被提出。这种方法是从另一种角度来解决问题，即不求出问题的精确极大或极小值解，而是求出与精确解“相去不远”的解。对其基本的原理可以参考[16]等书。在大量的NP难问题被提出以后（可以参考[26]），由于N P≠P的猜想愈来愈趋于真实，对这些问题求解精确解变得十分困难，而对这些问题设计好的近似算法成为研究的主要方向（可以参考[32]）。
定义4（PTAS）一个优化问题的多项式时间近似方案（PTAS）是一个近似算法，该算法的输入为问题的实例以及一个任意小的值ε> 0，满足这个方案是一个近似度为1 + ε的近似算法，并且对于每一个固定的ε，其运行时间对于实例的规模n是多项式的。
定义5（FPTAS）一个优化问题的完全多项式时间近似方案（FPTAS）是一个近似算法，该算法的输入为问题的实例以及一个任意小的值ε> 0，满足这个方案是一个近似度为1 + ε的近似算法，并且其运行时间对于实例的规模n以及1=ε是多项式的。
对一个问题设计的近似算法可以近似到什么程度？一个问题是否存在FPTAS、PTAS，或者存在一个常数近似度的算法？在PCP定理被证明以前，证明NP难的优化问题不可近似的方法很少，主要还是依靠设计巧妙的规约，在N P≠P的假设下，从一个NP-complete的问题的实例规约到优化问题的一个实例，并且满足，如果前者是属于这个语言的实例，那么后者存在一个目标值比较大（或者比较小）的解；如果前者不属于这个语言，那么后者的目标值就比较小（或者比较大）。使用这样的方法可以把一个实例在两种情况下的目标值之间的间隙“拉大”，而这个间隙，或者说两个目标值之比值就是其近似度的下界，当然，是在N P≠P 的前提下。
早期的这种规约对问题的依赖性比较大，有些问题能够找出这样的规约，而有些问题就没有找到这样的规约。比如说对一般情况下的旅行商问题，不存在任意常数近似度的近似算法就是通过Hamilton回路问题规约过去的。一类相似问题（Min-k-Clustering、Min-k-Center、Min-k-Supplier、Min-k-Switching Network）在[33]中被证明不存在某个常数近似度的近似算法，并且和已经发现的近似算法的近似度吻合了。但是对于其他大量的问题，比如说3-SAT、MinVertex Cover、Max-Cut等问题，就没有找到这种下界。
PCP定理从概率的角度重新刻画了NP类，如果x 2 L那么其接受的概率很大，反之很小。这样的间隙和前面提到的优化问题的目标值的间隙非常相似，在[22]中，使用了非常经典的一个规约，将这两者联系起来，从而可以将任意一个NP问题的PCP系统，规约到一个优化问题，并且满足两种情况下解的间隙很大，进而得到这个优化问题近似度的下界。在[3]中，Arora等人证明了存在一个常数ε，Max-3-SAT不存在ε近似度的近似算法。这个结论和1972年Cook证明的3-SAT是NP-complete语言有异曲同工之处，因为通过这个问题，以及问题之间的多项式时间规约，可以把不可近似的结论扩展到其他NP难的优化问题。
这个扩展只是一个研究方向的开始。在[3]中，这个ε的值非常小，与当时这个问题的最好的近似算法的近似度的差距还十分大，同样的问题也存在于其他大量的优化问题中。如何将近似度的上下界尽可能逼近成为此后研究的重点。这种改进被追溯到PCP模型本身，此后多种对PCP模型的改进，以及PCP模型中的新参数被提出，新的方法，例如多项式性质的测试、傅立叶变换、编码理论都被应用到其中，可以参考[51, 8, 9, 30, 23, 19, 31]。
此后，许多问题，如Min Set Cover[19]、Min Dominating Set、Max Clique[30]、Chromatic Number [23]，许多Max-SNP问题[31]的最好近似度，以及不可近似度的值都已经被吻合了。对于其他的NP难问题的最新进展，包括近似算法以及不可近似性的结论，可以参考Crescenzi和Kann给出的网站：http://www.nada.kth.se/theory/problemlist.html。
在这个方面，朱洪和他的同事及学生也进行了一些研究工作，主要是对于一些从实际应用中抽象出来的问题。比如内点带权的最小生成树问题，我们给出了2ln n的近似算法以及ln n的不可近似度[21]；多需求目标的UFL（Uncapacity Facility Location）问题，给出了log S + log T 的近似算法以及max{log S, log T}的不可近似度，其中S和T分别表示需要服务的结点数以及
https://www.wendangku.net/doc/473474377.html,
[60]
[58]；带测度函数的连通支配集问题，给出了1.1666的不可近似下界以及ln n + 3的近似算法[59]等。
张榜公钥模型下常数轮并发
—安全的可重置零知识证明和辩论系统Goldwasser在FOCS'97上的那篇著名的邀请报告的题目是：“二十年后的密码学的新方向
（或者，密码学和复杂性理论：天作之合）”。在此次报告中，Goldwasser宣称，过去20年当代密码学的最重大的进展是将密码学建立在计算复杂性的基础之上，并且正是计算复杂性理论将密码学从一门艺术发展成为一门严格的科学。Goldwasser指出，密码学和复杂性理论相互交织相互促进的最好见证就是零知识……
零知识证明系统在当代密码学中处于中心的位置，并且是定义和证明各种各样密码任务的广为接受的方法。伴随着互联网以及互联网上基于智能卡的电子商务的广泛普及和大规模应用，零知识证明系统在并发及可重置环境中运行时所遇到的安全问题，最近得到了高度重视和深入的研究。
大量和深入的最新研究已经证明，对于非平凡的语言常数轮（round）的并发及可重置的零知识系统，在没有Setup假设的朴素（plain）模型下是不存在的。为了得到常数轮的并发及可重置的零知识系统，一些著名的计算模型已经提出来，其中最弱同时最令人关注的是张榜公钥（Bare Public-Key）模型。不幸的是，至今我们不知道如何对非平凡的语言在张榜公钥模型下构造具有并发验证者安全（即并发可靠性及并发证据可提取性）的并发及可重置的零知识系统。也就是说，所有以前在张榜公钥模型下的并发及可重置的零知识系统，仅仅能保证并发证明者安全（即并发及可重置的零知识），却不能保证并发验证者安全（即并发可靠性及并发证据可提取性）。但是，在大多数基于互联网以及还有Mutit和基于智能卡的现实应用中（比如互联网上基于智能卡的安全电子商务），同时保证并发证明者安全和并发验证者安全的零知识系统是系统安全所必需的。
赵运磊、邓小铁、朱洪等的研究[55,56,57]显示，如何在广义公钥模型下构造实用的及一般的同时具有并发证明者安全和并发验证者安全，从而可以在并发及可重置环境中安全运行的零知识系统。因为零知识证明系统在当代密码学中处于中心的位置，并且由于互联网以及互联网上基于智能卡的电子商务的广泛普及和大规模应用，这些工作具有极其重要的理论和实际意义。
对于并发零知识，在张榜公钥模型下，对于常数轮且具有并发验证者安全（即并发可靠性及并发证据可提取性）的黑盒子（black-box）并发零知识和知识辩论（argument of knowledge）系统，我们给出了两个构造：一个是在离散对数假设下，对于所有具有§-协议的语言运行6轮但勿需经一般的NP-归约的实用构造；另一个是在单向函数假设下，对于所有NP-语言运行4轮（这是最优的）但需经一般的NP-归约的一般性构造。我们强调，无论是我们实用的构造还是一般性的构造，都代表了当代密码学在并发零知识领域的最新成就。
对于可重置零知识，我们引入了一个新的注册公钥模型：弱公钥（weak public-key，WPK）模型。弱公钥模型是恰好处于由Canetti、Goldreich、Gold-wasser和Micali在[12]中引入的张榜公钥模型，以及由Micali和Reyzin在[38]中引入的上界公钥（upper-bounded public-key，UPK）模型之间的一种注册公钥模型。弱公钥模型的合理性和优越性，在运行于分布式client/server
https://www.wendangku.net/doc/473474377.html,
型下，对所有NP-语言实现最少轮（3-round）同时具有并发可靠性的可重置零知识辩论系统。我们在WPK模型下关于具有并发可靠性的可重置零知识方面的工作，是对Micali和Reyzin在UPK模型下并发可靠的可重置零知识工作[39]的一个极其重要的改进和扩充。更为重要的是，由于对所有NP-语言常数轮且并发可靠的可重置零知识系统是否在张榜公钥模型中存在是一个著名的公开问题，我们此方面的工作对于解决这一重要公开问题，亦迈出了重要一步。
我们早在零知识证明的概念刚刚被Goldwasser、Micali和Rackoff[27, 28]提出时，就关注这方面的研究，给出NP类语言的4-轮零知识证明[61]。零知识（ZK）协议允许证明者给验证者证实一个定理而不泄漏任何其他（验证者在多项式时间内计算得不到的）知识。ZK有着多个极为重要应用。本文中使用证明（proof）和辩论（argument）两字，前者表示在协议中的证明者计算能力不限制，后者规定证明者计算能力限于多项式时间的但带有辅助信息即证据。ZK协议可以在许多环境（模型）中执行，可重置零知识（resettable zero-knowledge(rZK)）是当今最受关注的零知识协议。它起源于灵巧卡（smart-cards）或者其他设备被零知识证明者使用，而需防止恶意地重置初始条件，或者在每次新的调用时产生新的随机数以确保证明者的安全性。rZK还来源于异步网络（如互联网）中验证者无法通过并发地运行零知识协议而获得额外知识。事实上rZK是被Dwork、Naor和Sahai[18]所引入的并发零知识概念的推广和加强。简而言之，一个rZK协议具有性质如下：即使验证者并发地和证明者交互多项式次，每次用同样的起始格局和随机带，协议仍然是安全的。因为许多重要的论断出现于NP，ZK对NP语言显示出关键作用，除此之外，ZK对许多数论论断也有直接而有效的应用。一个主要直接的应用是身份验证（identication(ID)）[20]。然而，当ZK协议用于身份验证时，这些协议常常无法重置或者说，如果允许证明者可被重置，协议是不安全的。
交互式协议有效性的衡量测度是轮数。遗憾的是没有标准模型下的常数轮rZK协议，至少在黑盒模型下，Canetti、Killian、Petrank和Rosen[13, 14]指出没有常数轮rZK。为得到常数轮，rZK[12]引入具有吸引力的简单模型，bare public-key（BPK）张榜公钥模型。BPK模型直接了当地假设所有验证者（无论是诚实的和不诚实的）在任何用户们交互开始之前存放公钥在公共文件中2。但是，存放的公钥是惟一的还是不合法的（即根本没有对应的私钥）均未作规定[12]。对手可能注册许多虚假的没有任何担保的公钥。特别地，对手注册的公钥可能对手自己都不知道对应的私钥是什么，甚至更本就没有对应的私钥，这些我们均不得而知。BPK模型所保证的仅仅是限制潜在的对手不同身份的数目（对手能试图假冒任何公共文件中注册用户，但不能以非注册用户身份活动），除此以外，别无假设。BPK模型是非常简单的，事实上是常用的构成任何公钥密码系统和数字签名模块的公钥基础设施模型（public-key infrastructure (PKI) model）的弱版本。
形式化的rZK定义和BPK模型下并发可靠性成果叙述
BPK 模型由下面几部分组成：
●F是一个公钥文件，它具有多项式个记录（id, PK id），其中字符串id是验证者的身份，PK id是他或她声称的公钥。
●P(1n, x, w, F, id, γ)是一个诚实的证明者，它是一个polynomial-time交互机，1n是安全参数，x是L中一个n-位串，w是一个辅助输入即证据，F是一个公钥文件，id是验证者身份，γ是它的随机带。
●V是一个诚实的验证者，具有多项式时间的交互机。按以下两步工作：
1. 密钥产生阶段。V，基于安全参数1n和随机带γ，输出一个公钥PK且记住对应的密钥SK。
2. 验证阶段。V，基于输入SK，x 2 f{0, 1}n和随机带γ，和证明者运行交互协议，输出2BPK模型允许动态地注册公钥，如何处理动态公钥注册，参见[12]。
恶意的重置验证者和可重置的零知识
一恶意s-重置验证者V*，这里s是一个正多项式，是一个按两步运作的概率多项式时间（PPT）图灵机，1n是输入参数。
Stage-1. V*接受s(n)个每个长为n的distinct strings x1, …, x s(n)，且张榜公布一个公共文件F和一系列（不失去一般性）s(n) 个身份id1 ,…,id s(n)。
Stage-2. 从第一步的最后格局，s(n)个随机带，γ1, …, γs(n)，是随机地选出的，固定证明者P，因而产生s(n)3个确定性的证明者策略P(x i, id j, γk)，1≤I，j，k≤s(n)。于是V*把这s(n)3个证明者当作神喻，最后输出它的交互观察结果（即它的随机带和从神喻得到全部信息）。
定义6 （black-box resettable zero-knowledge）一个协议
分布1.V* 从随机均匀地选自γ1, …, γs(n) 的实验得到输出，V*运行的第一步得到F，然后V* 在第二步和P的s(n) 3个实例P(x i, w i, F, id j , γk)，1≤I, j, k≤s(n)，交互：注意到V*能够神喻地获得P的s(n) 3的实例。
分布2.输出S(x1, …, x s(n))。
定义7 （resettable witness indistinguishability rWI）一个
在文献[12]中，Canetti et al.首次给出NP的一个4-轮rWI证明。Dwork和Naor把轮数降低到2。
BPK 模型中的并发可靠性
对于诚实的验证者V，具有公钥PK 和密钥SK，一个s-并发恶意证明者P*。如果P*已经运行i－1 (1≤i－1≤s(n)) 次，他可以闲混地选择公共输入x i 2 {0; 1} n（它可以等于某x j，1≤j < i) ，开始新的一步V (SK, x i,ρi)。我们在此强调V在验证步用独立的随机带（即ρ1, …, ρs(n)是独立随机串）。
我们说一个协议满足BPK模型下并发可靠性concurrent soundness，如果对任意诚实验证者V，对所有正多项式s，所有s-并发恶意证明者P*，存在一个i（1≤i≤s(n)），使得V (SK, x i, ρi)输出“accept x i”而x i 62 L的概率是可忽略不计的。
Moti Yung和赵运磊[57]首次给出了任何NP-语言的5－轮并发可重置安全辩论（rZK-CS），该辩论是具有张榜公钥的。
对数空间的几种复杂类
确定性对数空间复杂性类（L）和非确定性对数空间复杂性类（NL）是两个传统的复杂性类，在上个世纪60年代就已经被提出，它们分别是基于确定图灵机和非确定图灵机这两个模型。在当时主要的研究方向之一就是两种模型之间关系，即给定同样的资源，是否非确定图灵机的计算能力比确定图灵机的要强，或者说是否非确定图灵机所识别的语言类要真包含确定图灵机所识别的语言类。L与NL的性质也被深入的研究。到了后来随机计算模型的提出，便有了随
https://www.wendangku.net/doc/473474377.html,
定义8 （RL）RL是这样的语言L的集合：存在一个随机图灵机M满足对任意输入x 2{0, 1}*，如果x 2 L则Prob[M(x) = 1]≥1/2，如果x 62 L则Prob[M(x) = 0] = 1，并且M使用的空间为O(log∣x∣)，时间为∣x∣的多项式。
定义9 （BPL）BPL是这样的语言L的集合：存在一个随机图灵机M满足对任意输入x 2 {0，1}*，如果x 2 L 则Prob[M(x) = 1]≥2/3，如果x 62 L 则Prob[M(x) = 1]≤1/3，并且M 使用的空间为O(log∣x∣)，时间为∣x∣的多项式。
在1982年，Lewis和Papadimitriou[37]提出了对称空间复杂性类SL。SL的提出是基于对空间复杂性的一种图刻画。对于图灵机计算的每一步，图灵机的状态以及输入带和工作带上的字符和指针位置都在发生改变，上面这些参数合在一起就构成了图灵机计算的一个格局，格局图就是图灵机对于一个输入所有格局以及格局之间的转化关系所构成的一个图，而对于判断给定的输入是否能被接受，就是验证是否在这个图中存在一条从起始格局到某个接受格局的一条路。可以看到，对于确定性图灵机和非确定性图灵机，其计算过程所对应的格局图分别是出度为1的有向图和出度为常数的有向图，图的顶点的个数为输入长度的多项式大小。并且知道给定一个森林以及森林中两个顶点，问是否存在这两个顶点之间的一条路径，这个问题是L-complete 的；而给定一个有向图以及图中的两个顶点，问是否存在这两个顶点之间的一条路径，这个问题是NL-complete的。现在把目光放到无向图的两点连通性问题上，这个问题是介于上面两个问题之间的，但是否是L-complete或者是NL-complete的？从这个问题出发，Lewis和Papadimitriou定义了对称图灵机，即在图灵机的计算过程中，如果有从某个格局到另一个格局的转化，那么必需存在后者到前者的转化。而SL类是在对称图灵机上使用对数空间可以接受的所有的语言的集合。
可以看出，无向图两点连通性问题是SL-complete的。所以，L μ SL μ NL。但是，SL与RL 的关系怎样？在1979年，Aleliunas等人[1]就已经证明了，无向图两点连通性问题是属于RL的，从而证明了SL μ RL。在他们的证明中，使用了随机行走的方法，即在图中从一点出发，随机沿着一条出边到达其相邻的顶点，按照这种方法进行下去，可以以很大的概率在多项式步内走遍图中每个顶点。
对于空间复杂性类的进展，一个很重要的方面就是证明了上述四个类在补下面是封闭的。首先是关于NL的结论，1988年，Immerman[35]和Szelepc-senyi[52]分别证明了NSpace(s(n)) = co ?NSpace(s(n))。在他们的证明中，使用了逐步计数和枚举的方法，记录从一个点出发在i步内可以到达的点的个数，i从1到n－1。当知道i步内能到达的点的个数求i + 1步内能到达的点的个数时，使用猜测加验证的方法，如果猜测错误就拒绝接受，因为是非确定的计算模型，这种方法能保证若在i时求得的值是正确的，那么在i + 1是求得的值也是正确的，因为不正确的都被拒绝了。其次是关于SL在补下封闭的结论，由Nisan和Ta-Shma[43]在1995年给出了证明。根据确定性图灵机和概率图灵机自身的对称性，可以看到，上述四种空间复杂性类在补下都是封闭的，更多相关结论可以参考Jenner的综述[36]。
通过Savitch[47]给出的模拟，即在格局图上递归使用二分查找法，可以证明SL、RL、NL 这些复杂性类都是包含在DSpace(log2(n))，即都是在确定空间log2 (n)中的。近年来对SL和RL 的确定空间的上界都有重大的进展。对于RL研究的发展得益于Nisan[40]提出的伪随机产生器。在这篇文章中，Nisan给出了使用种子长度为O(log2n)，并且产生的伪随机串的长度为多项式长的伪随机产生器的构造。虽然这个结果并没有直接改进Savitch的结果，但是这个伪随机产生器可以用来证明[41]无向图的连通性问题（实际上所有的BPL问题），可以在确定并行的多项式时间以及polylog空间内解决。这种问题类被称为Steve类（SC）。利用Nisan的伪随机产生器，Nisan、Szemeredi和Wigderson[42]证明了无向图的连通性问题可以在确定性空间O(log1:5 n)内解决。Saks和Zhou[46]将这个结论推广，证明了所有BPL问题可以在确定空间O(log1.5n)内解决。接着又由Armoni、Ta-Shma、Wigderson和Zhou[2]证明了无向图的连通性问题可以在确定空间O(log4/3n)内解决。在并行时间和空间界限方面，到目前最好的对RL和BPL模拟的结论由Cai、Chakaravarthy和Melkebeek[11]提出。他们证明了对于所有的0≤α≤0.5，BPL可以在确定并行
https://www.wendangku.net/doc/473474377.html, 的时间α和空间O(log n)内被模拟。
对于SL研究的一项突破是，由Trifonov[53]和Reingold[45]分别证明了SL的上界是DSpace(log(n)loglog(n))和L，这两篇文章都出现在2005年的STOC3上，并且被评为最佳论文。特别是后者，证明了SL坍塌到L。其文章使用了扩展图（expander graph）的方法，在不改变图的连通性的基础上，利用扩展图扩展性强的性质，通过不断将扩展图嵌入原图的方法，使得原图的直径降低为对数大小，这样只需枚举所有对数长度的路径就可以检测是否存在两点之间的路径。
目前，最新的方向就是研究RL和L的关系，很多学者都相信RL也是可以坍塌到L的。
结论
本文主要介绍了计算复杂性理论近期重大发展中的两个方面，但是这两个重大的进展也没有完全解决这两个方面的问题，比如说在NP难问题的不可近似性中，仍然有许多问题近似度的下界没有和它最好近似算法的近似度吻合，其中最突出的就是顶点覆盖问题（Vertex Cover Problem），这个问题的解决可能需要引入新的参数或者改进的模型；还有就是对数空间复杂性类的关系，现在只是证明了SL = L，但是RL是否和L相等，或者NL和L的关系如何还是未知。在复杂性理论中，还有很多类似于这些的未解决的问题，这些都有待计算机科学工作者的努力。
蔡进一博士，（美）University of Wioconsin at Madison计算机科学系教授，复旦大学信息科学与工程学院兼职教授。主要研究兴趣包括计算复杂性和计算机科学理论。
葛启复旦大学计算机科学系硕士研究生。
朱洪复旦大学计算机科学系教授，博士生导师，计算机理论教研室主任。主要研究兴趣包括算法和复杂性、量子计算，生物计算，计算密码学。担任中国计算机学会理论计算机科学专业学组常务理事、计算理论学组组长。
参考文献
[1] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász and C. Rackoff. Random Walks, “Universal Traversal Sequences, and the Complexity of Maze Problems”. In Proc. 20th Ann. IEEE Symp. on Foundation of Computer Science, pp. 218-223, 1979.
[2] R. Armoni, A. Ta-Shma, A. Wigderson and S. Zhou. “An O(log4/3n) space algorithm for (s,t) connectivity in undirected graphs”. J. of ACM, 47(2), pp.294-311, 2000.
[3] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. “Proof Verification and Hardness of Approximation Problems”. In Proc. 33rd Ann. IEEE Symp. on Foundation of Computer Science, pp. 14-23, 1992.
[4] S. Arora and S. Safra. “Probabilistic Checking of Proofs: A New Characterization of NP”. In Proc. 33rd Ann. IEEE Symp. on Foundation of Computer Science, pp. 2-13, 1992.
[5] L. Babai. “Trading Group Theory for Randomness”. In Proc. 17th Ann. ACM Symp. on Theory of Computing, pp. 421-429, 1985.
[6] L. Babai, L. Fortnow L. A. Levin and M. Szegedy. “Checking Computations in Polylogarithmic Time”. In Proc. 23rd Ann. ACM Symp. on Theory of Computing, pp. 21-31, 1991.
[7] L. Babai, L. Fortnow and C. Lund. “Non-deterministic Exponential Time has Two-prover Interactive Protocols”. In Proc. 31st Ann. IEEE Symp. On Foundation of Computer Science, pp. 16-25, 3Symposium on Theory of Computing，由美国计算机学会（ACM）主办
https://www.wendangku.net/doc/473474377.html, [8] M. Bellare, S. Goldwasser, C. Lund and A. Russell. “Effcient Probabilistically Checkable Proofs and Applications to Approximation”. In Proc. 25th Ann. ACM Symp. on Theory of Computing, pp. 294-304, 1993.
[9] M. Bellare, S. Goldwasser and M. Sudan. “Free Bits, PCPs and Non-approximability - towards Tight Results”. In Proc. 36th Ann. IEEE Symp.on Foundation of Computer Science, pp. 422-431, 1995.
[10] M. Ben-Or, S. Goldwasser, J. Kilian and A. Wigderson. “Multi-prover Interactive Proofs: How to Remove Intractability Assumptions”. In Proc. 20th Ann. ACM Symp. on Theory of Computing, pp. 113-131, 1988.
[11] Jin-yi Cai, Venkatesan T. Chakaravarthy and Dieter van Melkebeek. “Time-Space Tradeoff in Derandomizing Probabilistic Logspace”. STACS 2004, pp.571-583, 2004.
[12] R. Canetti, O. Goldreich, S. Goldwasser and S. Micali. “Resettable Zero-Knowledge”. In ACM Symposium on Theory of Computing, pages 235-244, 2000. Available from: http://www.wisdom.weizmann.ac.il/?oded/
[13] R. Canetti, J. Kilian, E. Petrank and A. Rosen. “Black-Box Concurrent Zero-Knowledge Requires ~-(log n) Rounds”. In ACM Symposium on Theory of Computing, pages 570-579, 2001.
[14] R. Canetti, J. Kilian, E. Petrank and A. Rosen. “Black-Box Concurrent Zero-Knowledge Requires (Almost) Logarithmically Many Rounds”. SIAM Journal on Computing, 32(1): 1-47, 2002.
[15] L. Carter and M. N. Wegman. “Universal Classes of Hash Functions”. https://www.wendangku.net/doc/473474377.html,put. Syst. Sci., 18(2), pp. 143-154, 1979.
[16] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. “Introduction to Algorithms, Second Edtion”. MIT Press, 2001.
[17] D. Du and K. Ko. “Theory of Computational Complexity”. John Wiley and Sons, 2000.
[18] C. Dwork, M. Naor and A. Sahai. “Concurrent Zero-Knowledge”. In ACM Symposium on Theory of Computing, pages 409-418, 1998.
[19] U. Feige. “A Threshold of ln n for Approximating Set Cover (Preliminary Version)”. In Proc. 28th Ann. ACM Symp. on Theory of Computing, pp.314-318, 1996.
[20] U. Feige, A. Fiat and A. Shamir. “Zero-knowledge Proof of Identity”. Journal of Cryptology, 1(2): 77-94, 1988.
[21] Rudolf Fleischer, Qi Ge, Jian Li, Shijun Tian, and Haitao Wang. “Approximating Spanning Trees With Inner Nodes Cost”. Submitted to The Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies.
[22] U. Feige, S. Goldwasser, L. Lovasz, S. Safra and M. Szegedy. “Approximating Clique is Almost NP-complete”. In Proc. 32nd Ann. IEEE Symp. On Foundations of Computer Science, pp. 2-12, 1991.
[23] U. Feige and J. Kilian. “Zero Knowledge and the Chromatic Number”. In Proc. 11th Ann. IEEE Conference on Computational Complexity, pp. 278-287, 1996.
[24] L. Fortnow, J. Rompel and M. Sipser. “On the Power of Multi-prover Interactive Protocols”. In Proc. 3rd Ann. IEEE Conference on Structure in Complexity Theory, pp. 156-161, 1988. Erratum in Proc. 5th Ann. IEEE Conference on Structure in Complexity Theory, pp. 318-319, 1990.
[25] U. Feige and Shamir. “Zero-Knowledge Proofs of Knowledge in Two Rounds”. In G. Brassard (Ed.): Advances in Cryptology-Proceedings of CRYPTO1989, LNCS 435, pp. 526-544. Springer-Verlag, 1989.
[26] M. R. Garey and D. S. Johnson. “Computers and Intractability: a guide to the theory of NP-completeness”. W. H. Freeman and Company, 1979.？
[27] S. Goldwasser, S. Micali and C. Rackoff. “The Knowledge Complexity of Interactive Proof Systems”. In Proc. 17th Ann. ACM Symp. on Theory of Computing, pp. 291-304, 1985 and SIAM https://www.wendangku.net/doc/473474377.html,puting, 18 186-208 1989.
[28] O. Goldreich, S. Micali and A. Wigderson. “Proofs that Yield Nothing But Their Validity or All language in NP Have Zero-Knowledge Proof Systems”. Journal of the Association for Computing Machinery, 38(1): 691-729, 1991.
[29] S. Goldwasser and M. Sipser. “Private Coins versus Public Coins in In-teractive Proof Systems”. In Proc. 18th Ann. ACM Symp. on Theory of Computing, pp. 59-68, 1986.
https://www.wendangku.net/doc/473474377.html,
1?2”
Foundation of Computer Science, pp. 627-636, 1996.
[31] J. H?stad. “Some Optimal Inapproximability Results”. In Proc. 29th Ann. ACM Symp. on Theory of Computing, pp. 1-10,1997.
[32] D. S. Hochbaum (ed.). “Approximation Algorithm for NP-Hard Problem”. PWS Publishing Company, 1997.
[33] D. S. Hochbaum and D. B. Shmoys. “A Unifed Approach to Approximation Algorithms for Bottleneck Problems”. J. ACM, (33), pp. 533-550, 1986.
[34] J. Hopcroft and J. Ullman. “Introduction to Automata Theory, Language and Computation.”Addison-Wesley, 1979.
[35] N. Immerman. “Nondeterministic Space is Closed under Complementation”. SIAM J. on Computing, (17), pp. 760-778, 1988.
[36] B. Jenner. “Closure under Complementation of Logspace Complexity Classes- A Survey”. Foundations of Computer Science: Potential - Theory - Cog-nition, pp. 163-175, 1997.
[37] H. R. Lewis and C. H. Papadimitriou. “Symmetric Space-bounded Compu-tation”. Theoretical Computer Science, (19), pp. 161-187, 1982.
[38] S. Micali and L. Reyzin. “Soundness in the Public-Key Model”. In J. Kilian(Ed.): Advances in Cryptology-Proceedings of CRYPTO 2001, LNCS 2139, pp. 542-565. Springer-Verlag, 2001.
[39] S. Micali and L. Reyzin. “Min-Round Resettable Zero-Knowledge in the Public-Key Model”. In
B. Pˉtzmann (Ed.): Advances in Cryptology-Proceedings of EUROCRYPT 2001, LNCS 2045, pp. 373-393. Springer-Verlag, 2001.
[40] N. Nisan. “Pseudorandom generators for space-bounded computation”. Com-binatorica, 12(4), pp. 449-461, 1992.
[41] N. Nisan. “RL μ SC”. In Proc. 24th Ann. ACM Symp. on Theory of Com-puting, pp. 619-623, 1992.
[42] Noam Nisan, Endre Szemerédi and Avi Wigderson. “Undirected connectivity in O(log1:5 n) space”. In Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, pp. 24-29, 1992. [43] N. Nisan and A. Ta-Shma. “Symmetric Logspace is Closed under Complement”. In Proc. 27th Ann. ACM Symp. on Theory of Computing, pp.140-146, 1995.
[44] C. H. Papadimitriou. “Computational Complexity”, Addison-Wesley, 1994.
[45] O. Reingold. “Undirected ST-Connectivity in Log-Space”. In Proc. 37th Ann. ACM Symp. on Theory of Computing, to appear.
[46] M. Saks and S. Zhou. “BP H SPACE(S) μDSPACE(S3=2)”. Journal of Computer and System Sciences, 58, pp. 376-403, 1999.
[47] W. J. Savitch. “Relationships between nondeterministic and deterministic tape complexities”. J. of Computer and System Sciences, 4(2), pp. 177-192, 1970.
[48] A. Shamir. “IP=PSPACE”. In Proc. 31st Ann. IEEE Symp. on Foundations of Computer Science, pp. 11-15, 1990.
[49] M. Sipser. “Introduction to the Theory of Computation”. PWS Publishing Company, 1997.
[50] L. Stockmeyer. “The Complexity of Approximate Counting”. In Proc. 15th Ann. ACM Symp. on Theory of Computing, pp. 118-126, 1983.
[51] M. Sudan. “Effcient Checking of Polynomials and Proofs and the Hardness of Approximation Problems”. Springer-Verlag. Lecture Notes on Computer Science, 1001.
[52] R. Szelepcsenyi. “A Method of Forced Enumeration for Nondeterministic Automata”. Acta Informatica, (26), pp. 279-284, 1988.
[53] V. Trifonov. “A O(log n log log n) Space Algorithm for Undirected Connectivity”. In Proc. 37th Ann. ACM Symp. on Theory of Computing, to appear.
[54] L. G. Valiant and V. V. Vazirani. “NP Is as Easy as Detecting Unique Solutions”. Theoretical Computer Science, Vol. 47 (1), pp. 85-93, 1986.
[55] Y. Zhao. “Concurrent Zero-Knowledge with Concurrent Soundness in the Bare Public-Key Model”. Cryptology ePrint Archive: Report 2003/265.
[56] Y. Zhao, X. Deng, C. H. Lee and H. Zhu. “Resettable Zero-Knowledge in the Weak Public-Key Model”. In E. Biham (Ed.): Advances in Cryptology-Proceedings of EUROCRYPT 2003, LNCS 2656 ,
https://www.wendangku.net/doc/473474377.html, [57] M. Yung and Y. Zhao. “Recent Advances on Zero-Knowledge: Constant-Round Concurrently-Secure rZK with (Real) Bare Public-Keys”. ECCC 12(48), 2005. Report No. 2005-048 [58] Yong Zhang and Hong Zhu. “An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs”. COCOON 2004, pp.143-150, 2004.
[59] 马俊, 朱洪. 带测度函数的连通支配集问题. 将刊登在计算机科学2006年第1期
[60] 田世俊, 朱洪. 多需求目标的UFL问题及其近似算法. 被2005年中国理论计算机科学年会接受，将刊登在计算机科学2005年第8期
[61] 周玉林, 熊鹏荣, 朱洪, 石凤仙. 随机自归约的一个四步零知识证明协议. 计算机研究与发展35(11) 1000-1003, 1998
浅谈计算复杂性理论
浅谈计算复杂性理论 任忠 乌鲁木齐石化公司计控中心 摘要：本文阐述了计算复杂性理论的产生、定义、研究内容和发展。 关键词：算法分析；计算复杂性；起源；发展 1.计算法复杂性理论的起源 在几千年的数学发展中，人们研究了各式各样的计算，创立了许多算法。但是，以计算或算法本身的性质为研究对象的数学理论，却是在20世纪30年代才发展起来的。 1936年，为了讨论对于每个问题是否都有求解算法，数理逻辑学家提出了几种不同的计算模型的定义。K.Godel和S.C.Kleene等人创立了递归函数论，将数论函数的算法、可计算性刻画为递归可枚举性。A.M.Turing和E.L.Post提出了理想计算机的概念，将问题算法可解性刻画为在具有严格定义的理想计算机上的可解性。40年代以后，随着计算机科学技术的发展，研究的焦点从理论可计算法转移到现实可计算性上。人们不仅需要研究理论上的、原则上的可计算性，还要研究现实的可计算性，即研究计算一个问题类需要多少时间，多少存储空间，研究哪些问题是现实可计算的，哪些问题虽然原则上可计算，但由于计算的量太大而实际上无法计算等。因而一般算法设计方法研究和对一类问题算法解的难度分析便成为计算机科学的热点。此后，计算复杂性的研究等不断有所发展。由此产生了算法学和计算复杂性理论等新兴研究领域。 计算复杂性大的进展始于50年代末、60年代初，当时在美国有两个并行的中心，一个是通用电气公司设立于纽约州Schenectady的研究实验室，核心人物是J.Hartmanis和R.Stearns。1964年11月，他们在普林斯顿举行的第五届开关电路理论和逻辑设计学术年会上发表了论文"Computational Complexity of recursivese quences"，论文中首次使用了"计算复杂性"这一术语，由此开辟了计算机科学中的一个新领域，并为之奠定了理论基础。他们两人是1993年度图灵奖获得者。另一个中心是麻省理工学院MIT，在那里，加州大学伯克利分校著名的计算机科学家Manuel Blum与前述两人互相独立地进行着相关问题的研究，并完成了他的博士论文："Amachine independent theory of the complexity of recur- sive functions"，Blum是受以色列学者M.O.Rabin的启发而开始这方面的研究的。Rabin 是希伯莱大学的教授，是研究计算复杂性问题的先驱，并在1976年荣获图灵奖。Blum的论文不但提出了有关计算复杂性的一些公理，而且在对复杂性类的归纳上也比其他学者有更高的抽象度。因此布、哈、斯三人被学术界公认为计算复杂性理论的主要奠基人。
(完整word版)简单的时间计算
简单的时间计算 教学内容：青岛版三年级下册第67—68页信息窗1第2个红点及“自主练习”第3—7题。 教学目标： 1．结合生活实际，学生自主探究计算经过时间的算法，培养学生的推理能力和独立思考的习惯。 2．掌握求简单的经过时间的方法，正确解答一些求经过时间的实际问题，体会简单的时间计算在生活中的应用。 3．建立时间观念，体会合理安排时间的重要性，养成珍惜时间的良好习惯。 4．体会数学在现实生活中的应用，增强学习数学的兴趣和信心，培养运用知识的能力。 教学重难点： 教学重点：自主探究并掌握计算经过时间的算法，能解决实际生活问题。 教学难点：能正确地进行简单的时间计算。 教具、学具： 多媒体课件、钟表、学生练习用的活动钟面。 教学过程： 一、创设情境，提出问题 引导：同学们，走进天文馆，上节课我们学习了24时计时法，今天我们继续到天文馆看看还有哪些新知识等 待我们去发现？ 课件出示情境图，提问：我们 是怎样用24时计时法表示时间的 呢？生活中哪些地方用24时计时 法表示时间？（学生联系生活实际 说一说。） 让学生仔细观察画面，找出数学信息。 预设1：天文馆的开馆时间是8:30～16:30 预设2：科教片今日放映的片名和安排是：
《宇宙旅行》 9:00 《恐龙灭绝与天体碰撞》 10:30 《奇妙的星空》 15:00 《小丽访问哈勃》 15:45 引导：根据这些信息，你能提出哪些数学问题？（教师有选择的将问题板书在黑板上） 学生可能提出的问题预设： 问题1：天文馆每天开馆多长时间？ 问题2：从《恐龙灭绝与天体碰撞》开映到《奇妙的星空》开映间隔时间有多长？ 问题3：《小丽访问哈勃》播放了多长时间？ …… 引导：大家可真了不起，提出了这么多的问题，针对同学们提出的问题，这节课我们一起来研究简单的时间计算（板书课题）！ 【 设计意图：由信息窗情境图导入，引导学生观察、提出有关时间的问题，不仅培养了学生的问题意识，同时也培养学生用数学的眼光观察生活的能力，让学生体会身边的数学。】 二、自主学习，小组探究 引导：现在让我们一起去解决问题吧，请大家尝试解决：开馆时间
CASTEP计算理论总结+实例分析
CASTEP 计算理论总结 XBAPRS CASTEP 特点是适合于计算周期性结构，对于非周期性结构一般要将特定的部分作为周期性结构，建立单位晶胞后方可进行计算。CASTEP 计算步骤可以概括为三步：首先建立周期性的目标物质的晶体；其次对建立的结构进行优化，这包括体系电子能量的最小化和几何结构稳定化。最后是计算要求的性质，如电子密度分布(Electron density distribution)，能带结构(Band structure)、状态密度分布(Density of states)、声子能谱(Phonon spectrum)、声子状态密度分布(DOS of phonon)，轨道群分布(Orbital populations)以及光学性质(Optical properties)等。本文主要将就各个步骤中的计算原理进行阐述，并结合作者对计算实践经验，在文章最后给出了几个计算事例，以备参考。 CASTEP 计算总体上是基于DFT ，但实现运算具体理论有： 离子实与价电子之间相互作用采用赝势来表示； 超晶胞的周期性边界条件； 平面波基组描述体系电子波函数； 广泛采用快速fast Fourier transform (FFT) 对体系哈密顿量进行数值化计算； 体系电子自恰能量最小化采用迭带计算的方式； 采用最普遍使用的交换-相关泛函实现DFT 的计算，泛函含概了精确形式和屏蔽形式。 一， CASTEP 中周期性结构计算优点 与MS 中其他计算包不同，非周期性结构在CASTEP 中不能进行计算。将晶面或非周期性结构置于一个有限长度空间方盒中，按照周期性结构来处理，周期性空间方盒形状没有限制。之所以采用周期性结构原因在于：依据Bloch 定理，周期性结构中每个电子波函数可以表示为一个波函数与晶体周期部分乘积的形式。他们可以用以晶体倒易点阵矢量为波矢一系列分离平面波函数来展开。这样每个电子波函数就是平面波和，但最主要的是可以极大简化Kohn-Sham 方程。这样动能是对角化的，与各种势函数可以表示为相应Fourier 形式。 ```2[()()()]``,,k G V G G V G G V G G C C ion H xc i i k G GG i k G δε∑++-+-+-=++ 采用周期性结构的另一个优点是可以方便计算出原子位移引起的整体能量的变化，在CASTEP 中引入外力或压强进行计算是很方便的，可以有效实施几何结构优化和分子动力学的模拟。平面波基组可以直接达到有效的收敛。 计算采用超晶胞结构的一个缺点是对于某些有单点限缺陷结构建立模型时，体系中的单个缺陷将以无限缺陷阵列形式出现，因此在建立人为缺陷时，它们之间的相互距离应该足够的远，避免缺陷之间相互作用影响计算结果。在计算表面结构时，切片模型应当足够的薄，减小切片间的人为相互作用。 CASTEP 中采用的交换-相关泛函有局域密度近似（LDA ）（LDA ）、广义梯度近似（GGA ）和非定域交换-相关泛函。CASTEP 中提供的唯一定域泛函是CA-PZ ，Perdew and Zunger 将Ceperley and Alder 数值化结果进行了参数拟和。交换-相关泛函的定域表示形式是目前较为准确的一种描述。 Name Description Reference PW91 Perdew-Wang generalized-gradient approximation, PW91 Perdew and Wang PBE Perdew-Burke-Ernzerhof functional, PBE Perdew et al. RPBE Revised Perdew-Burke-Ernzerhof functional, RPBE Hammer et al.
苏教版三年级数学下册-简单的时间计算方法教案
简单的时间计算方法 教材第53~55页的内容。 1.利用24时记时法的相关知识和在生活中对经过时间的感受,探索简单的时间计算方法。 2.在运用不同方法计算时间的过程中,体会简单的时间计算在生活中的应用,建立时间观念,养成珍惜时间的好习惯。 3.进一步培养学生课外阅读的兴趣和多渠道收集信息的能力。 1.会进行简单的时间计算。 2.理解进行简单的时间计算的算理。 课件,图片,钟表。 老师:同学们,你喜欢过星期天吗?谁愿意给大家说一说星期天你是怎么安排的? 老师:明明的星期天是怎么安排的呢?让我们一起看看吧! (多媒体动态显示明明星期天的时间安排) 7:30 起床 7:40—8:20 早锻炼 8:30—9:00 吃早饭 9:00—11:00 看书、做作业 老师:看了明明星期天的时间安排,你知道了什么?为什么?你还想知道什么? 学生甲:明明吃早饭用了半个小时。因为从8:30—9:00经过了30分钟,也就是半个小时。 学生乙:我还想知道明明做什么事情用的时间最长。 1.老师谈话:明明在星期天做了不少的事,做每件事都用一些时间。每个小组从中选出两三件事情,计算一下各用了多长时间。 (1)分组学习,集体交流。说说学习过程中遇到哪些困难。 (2)集体汇报、订正。 学生提出问题,教师点击相关画面。 学生甲:从9:00—11:00经过了多长时间? 老师:哪位同学回答一下? 学生乙:11-9=2(时) 经过了2小时。 学生丙:明明锻炼用了多长时间? 老师:从7时40分到8时经过了多少分钟?(20分)从8时到8时20分经过了多少分
钟?(20分)一共经过了多少分钟?〔20+20=40(分)〕 老师:同学们,你们每天都用多长时间锻炼身体呢?如果能够坚持,相信你的身体一定会很棒! 2.教学例题。 老师出示例题。 老师:从这么多的信息中,你知道了什么?为什么? 学生甲:《智慧树》是8:10分开始播放。 学生乙:我知道《异想天开》是16:00开始播放。 老师:那么《动画剧场》播放了多长时间? 学生甲:《动画剧场》从14:00开始播放,16:00结束。 学生乙:我可以在钟面上数一数。 学生丙:我画图看一看。 学生丁:我还可以用减法计算。16-14=2(时)。 老师板书:16-14=2(时) 答:《动画剧场》播放2小时。 3.老师出示教材第54页“想想做做”第1题。 中午借书时间:13-12=1(时) 下午借书时间:17-15=2(时) 每天借书时间:2+1=3(时) 答:每天的借书时间有3小时。 4.老师:我们已经学习了一些计算经过时间的方法,不知同学们掌握得怎么样了。我们一起做一个练习吧! 一辆客车18时20分从北京开车,21时40分到达石家庄。路上用了多长时间? (1)说一说18时20分和21时40分分别表示什么? (2)动手拨一拨,算一算这辆客车在路上行了多长时间? (3)用线段图来表示。 学生:从18时20分到21时20分中间经过3小时,从21时20分到21时40分又经过20分,所以这辆客车在路上行了3小时20分钟。 1.说说你是怎样计算的。 (1)17时是下午几时?23时是晚上几时? (2)小力每天早上7时40分到校,11时50分放学回家,他上午在校多长时间? (3)从上海开往某地的火车,早上5时54分开车,当天19时57分到达。路上用了多长时间? 2.填空题。
小学五年级数学《时间的计算》教案模板三篇
小学五年级数学《时间的计算》教案模板三篇时间的简单计算对于学生来说有一定的难度，因为时间的进率是60，而我们平时的计算一般是退一做十的。下面就是我给大家带来的小学五年级数学《时间的计算》教案模板，欢迎大家阅读! 小学五年级数学《时间的计算》教案模板一 教学目标： 1、加深对时间单位的认识。 2、了解时间的知识在生活中的实际用途，会通过观察、数格子、计算来知道所经过的时间。 3、了解生活中处处有数学知识。 教学重点： 学会一些有关时间的计算。 教学准备： 教师准备多媒体课件。 教学过程： 一、复习旧知 1、时、分、秒进率 板书：1时=60分1分=60秒 2、填空题 2时=()分2分=()秒 180分=()时120秒=()分
1时40分=()分6分=()秒 3、填合适的时间单位 (1)一节课的时间是40()。 (2)看一场电影要2()。 (3)小东跑一100米要用16()。 二、探究新知 1、小学作息时间表 多媒体课件展示“小学作息时间表”学生自读问题，依次解决问题 (1)上午第一节课是从几时几分到几时几分?这一节课上了多少时间? 你是怎么知道一节课的时间，你有什么方法?你会不会列算式。 (老师讲解列算式计算) 板书：8：50–8：10=40分 8：50 -8：10 40 答：这节课上了40分钟。 (2)反馈练习：学生板演，说说自己怎么想的。 下午第七节课上了多少时间? (3)深入探究，10：50~11：30第四节上了多少时间? 学生先试做，问在计算中发现有什么问题? 重点讲解分不够减，到时退一作60分。 (4)反馈练习：1.小明从家里出发去学校，路上经历了多长时间?先看钟表，
3 计算复杂性理论
计算复杂性理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。 目录 [隐藏] ? 1 简介 ? 2 历史 ? 3 基本概念和工具 o 3.1 计算模型与计算资源 o 3.2 判定性问题和可计算性 o 3.3 算法分析 o 3.4 复杂性类 o 3.5 归约 ? 4 NP与P关系问题及相关理论 o 4.1 NP和P的定义 o 4.2 NP与P关系问题 o 4.3 NP完备理论 o 4.4 电路复杂性 o 4.5 其它NP与P关系问题相关的理论 ? 5 理论与实践 ? 6 参考 ?7 外部链接 [编辑]简介 计算复杂性理论所研究的资源中最常见的是时间（要通过多少步才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。 时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。 空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字（word）属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。
复杂度理论和可计算性理论不同，可计算性理论的重心在于问题能否解决，不管需要多少资源。而复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。 [编辑]历史 在20世纪50年代，Trahtenbrot和Rabin的论文被认为是该领域最早的文献。而一般说来，被公认为奠定了计算复杂性领域基础的是Hartmanis和Stearns 的1960年代的论文On the computational complexity of algorithms。在这篇论文中，作者引入了时间复杂性类TIME(f(n))的概念，并利用对角线法证明了时间层级定理（Time Hierarchy Theorem）。 在此之后，许多研究者对复杂性理论作出了贡献。期间重要的发现包括：对随机算法的去随机化（derandomization）的研究，对近似算法的不可近似性（hardness of approximation）的研究，以及交互式证明系统（Interactive proof system）理论和零知识证明（Zero-knowledge proof）等。特别的复杂性理论对近代密码学的影响非常显著，而最近，复杂性理论的研究者又进入了博弈论领域，并创立了“算法博弈论”（algorithmic game theory）这一分支。 该领域重要的研究者有（不完全列表）： ?史提芬·古克 ?姚期智（Andrew Chi-Chih Yao） ?Allan Borodin ?Manuel Blum ?Juris Hartmanis ?Richard Karp ?Leonid Levin ?Alexander Razborov ?Michel Sipser ?Avi Wigderson ?Walter Savitch ?Richard Stearns ?Lance Fortnow ?V. Arvind ?Lazlo Babai [编辑]基本概念和工具 [编辑]计算模型与计算资源
青岛版数学三年级下册简单的时间计算 )
简单的时间计算 [教学内容]《义务教育教科书·数学（三年级下册）》67～68页。 [教学目标] 1.结合生活实际，学生自主探究计算经过时间的算法，培养学生的推理能力和独立思考的习惯。 2.掌握求简单的经过时间的方法，正确解答一些求经过时间的实际问题，体会简单的时间计算在生活中的应用。 3.建立时间观念，体会合理安排时间的重要性，养成珍惜时间的良好习惯。 4.体会数学在现实生活中的应用，增强学习数学的兴趣和信心，培养运用知识的能力。 [教学重点]自主探究并掌握计算经过时间的算法，能解决实际生活问题。 [教学难点]能正确地进行简单的时间计算。 [教学准备]教具：多媒体课件、演示钟表；学具：学生练习用的活动钟面。 [教学过程] 一、创设情境，提出问题 师：同学们，走进天文馆，上节课我们学习了24时计时法，今天我们继续到天文 图1 ：科教片今日放映的片名和安排是：
【温馨提示】1.找一找：天文馆什么时间开门，什么时间结束？2.利用你手中的材料，大胆地拨一拨、画一画、数一数，想办法算一算。二、合作探索 图2 预设2：从《恐龙灭绝与天体碰撞》开映到《奇妙的星空》开映间隔时间有多长？ 预设3：《小丽访问哈勃》播放了多长时间？…… 师：大家可真了不起，提出了这么多的问题，针对同学们提出的问题，这节课我们一起来研究简单的时间计算（板书课题）！ 【设计意图】由信息窗情境图导入，引导学生观察、发现、并提出有关时间的问题，不仅培养了学生的问题意识，同时也培养学生用数学的眼光观察生活的能力，让学生体会身边的数学。 二、自主学习，小组探究 师：现在大家开始研究问题，如果遇到困难，可以请老师帮忙。 学生根据探究提示尝试解决，教师巡视指导，及时了解学生的学习情况 【设计意图】对学生进行大胆地放手，让学生自己经历探究经过时间的过程，温馨提示也仅是简单的对学生进行引导运用探究材料，教师不能代其劳，学生才能通过不同的方法，探索怎样求经过时间，感受探究的乐趣，提高解决问题的的能力和锻炼思维能力。 三、汇报交流，质疑评价 （一）学习不借位减 师：老师发现大家刚才研究的都非常的认真！哪个小组愿意将你们小组的想法与大家一起分享一下？ 预设1：数一数，我是数的，从8:30开始数，9:30、10:30……到16：30正好是8个小时。 预设2：画一画，我是画的，在时间轴上，从8:30到16：30正好经过了8个小时。
流体计算理论基础讲解
流体计算理论基础 1 三大基本方程 连续性方程 连续性方程也称质量守恒方程，任何流动问题都必须满足质量守恒定律，该定律可表示为：单位时间内流体微元中质量的增加等于同一时间间隔内流入该微元体的净质量，其形式如下： ()()()0u v w t x y z ρρρρ????+++=???? 可以写成： ()0div u t ρ ρ?+=? 其中ρ密度，t 为时间，u 为速度矢量，u ，v 和w 为速度矢量在x ，y 和z 方向上的分量。 若流体不可压缩，密度为常数，于是： 0u v w x y z ???++=??? 若流体处于稳态，则密度不随时间变化，可得出： ()()() 0u v w x y z ρρρ???++=??? 动量守恒定律 该定律可以表述为：微元体中流体的动量对时间的变化率等于外界作用在该微元体上的各种力之和，该定律实际是牛顿第二定律，按照这一定律，可导出x ，y 和z 三个方向上的动量守恒方程： ()()() ()()()yx xx zx x xy yy zy y yz xz zz z u p div uu F t x x y z u p div uv F t y x y z u p div uw F t z x y z τττρρτττρρτττρρ??????+=-++++? ?????????????+=-++++??????? ??????+=-++++???????? 式中，p 为微元体上的压力，xx τ，xy τ和xz τ等是因分子粘性作用而产生的作用在微元体表
面上的粘性应力τ的分量。x F ，y F 和z F 是微元体上的体力，若体力只有重力，且z 轴竖直向上，则：0,0x y F F ==，z F g ρ=-。 对于牛顿流体，粘性应力τ与流体的变形率成比率，有： x yy x 2();==()2();==()2();==()xx xy y xz z zz yz zy u u v div u x y x v u w div u x z x w v w div u x z y τμλττμτμλττμτμλττμ???? =++????? ???? =++????? ???? =++????? 其中，μ为动力粘度，λ为第二粘度，一般可取2 3 λ=- ，将上式代入前式中为： ()()()() ()()()()()u v w u p div uu div gradu S t x v p div uv div gradv S t y w p div uw div gradw S t z ρρμρρμρρμ???+=-+???? ???+=-+? ??????+=-+? ??? 其中： ()()/()/()/grad x y z =??+??+?? μ为动力粘度(dynamic viscosity)，λ为第二粘度(second viscosity),一般可取： 2 3 λ=-(参考文献：,Boundary Layer Theory,8th ed,McGraw Hill, New York,1979)。u S ,v S 和w S 为动量守恒方程中的广义源项，u x x S F S =+，v y y S F S =+，w z z S F S =+，而其中 x S ，y S 和z S 表达式为： ()()()(())()()()(())()()()(()) x y z u v w S div u x x y x x x x u v w S div u x x y y x y y u v w S div u x z y z x z z μμμλμμμλμμμλ????????=+++????????????????? =+++????????????????? =+++????????? 一般来讲，x F ，y F 和z F 是体积力在x ，y ，z 方向上的分量。x S ，y S 和z S 是小量，对于粘性为常数的不可压缩流体，0x y z S S S ===，动量守恒，简称动量方程，也称N-S 方程。 关于牛顿体与非牛顿体的定义如下：
小学三年级数学《简单的时间计算》教案范文三篇
小学三年级数学《简单的时间计算》教案范文三篇时间计算是继二十四时计时法的学习之后安排的一个内容。下面就是小编给大家带来的小学三年级数学《简单的时间计算》教案范文，欢迎大家阅读! 教学目标： 1、利用已学的24时记时法和生活中对经过时间的感受，探索简单的时间计算方法。 2、在运用不同方法计算时间的过程中，体会简单的时间计算在生活中的应用，建立时间观念，养成珍惜时间的好习惯。 3、进一步培养课外阅读的兴趣和多渠收集信息的能力。 教学重点： 计算经过时间的思路与方法。 教学难点： 计算从几时几十分到几时几十分经过了多少分钟的问题。 教学过程： 一、创设情景，激趣导入 1、谈话：小朋友你们喜欢过星期天吗?老师相信我们的星期天都过得很快乐!明明也有一个愉快的星期天，让我们一起来看看明明的一天，好吗? 2、小黑板出示明明星期天的时间安排。 7：10-7：30 起床、刷牙、洗脸; 7：40-8：20 早锻炼; 8：30-9：00 吃早饭; 9：00-11：00 看书、做作业 …… 3、看了刚才明明星期天的时间安排，你知道了什么?你是怎么知道的?你还想知道什么?
二、自主探究，寻找方法 1、谈话：小明在星期天做了不少的事，那你知道小明做每件事情用了多少时间吗?每 个小组从中选出2件事情计算一下各用了多少时间。 (1)分组学习。 (2) 集体交流。 2、根据学生的提问顺序学习时间的计算。从整时到整时经过时间的计算。 (1)学生尝试练习9：00-11：00明明看书、做作业所用的时间。 (2)交流计算方法：11时-9时=2小时。 3、经过时间是几十分钟的时间计算。 (1)明明从7：40到8：20进行早锻炼用了多少时间呢? 出示线段图。 师：7：00-8：00、8：00-9：00中间各分6格，每格表示10分钟，两个线段下边 的箭头分别指早锻炼开始的时间和结束的时间，线段图涂色部分表示早锻炼的时间。谈话：从图上看一看，从7时40分到8时经过了多少分钟?(20分)从8时到8时20分又经过 了多少时间?所以一共经过了多少分钟。(20+20=40分)小朋友们，如果你每天都坚持锻炼 几十分钟，那你的身体一定会棒棒的。 (2)你还能用别的方法计算出明明早锻炼的时间吗?(7：40-8：40用了一个小时，去掉 多算的20分，就是40分。或者7：20-8：20用了1个小时，去掉多算的20分，就是 40分。) (3)练习：找出明明的一天中做哪些事情也用了几十分钟? 你能用自己喜欢的方法计算出明明做这几件事情用了几十分钟吗?你是怎么算的? 三、综合练习，巩固深化 1、想想做做1：图书室的借书时间。你知道图书室每天的借书时间有多长吗? 学生计算。 (1)学生尝试练习，交流计算方法。 (2)教师板书。 2、想想做做2。 (1)学生独立完成。 (2)全班交流。
计算简单的经过时间练习题
课题：简单的经过时间的计算 教学内容：苏教版三年级上册第5单元24时计时法第二课时简单的经过时间的计算P53-55. 教学期望（目标）： 1、使学生结合生活实际，自主探究计算经过时间的算法，能够初步掌握一些求简单的经过时间的方法，能正确解答一些求经过时间的实际问题，进一步发展学生的推理能力。 2、在运用不同方法计算时间的过程中，体会简单的时间计算在生活中的应用，建立时间观念，体会合理安排时间的重要性，养成珍惜时间的良好好习惯。 3、进一步了解数学在现实生活中的应用，增强学习数学的兴趣和信心，进一步培养独立思考的习惯。 教学过程教学内容（教材、生活等教学资源）重组教学策略 (互动或讲述等) 预期 效果 导入新授一、创设问题情境，探究计算方法 （1）同学们，你们喜欢看电视吗？ （2）出示节目表： 你会选择收看哪个节目？ 你知道这个节目是什么时候开始？又是什 么时候结束的？ （一）整时段时间的计算 （1）你知道“六一剧场播”放多长时间吗？ 自己先想一想，再把你的想法在四人小组说 一说。 反馈方法： 数一数：从14：00到15：00是1小时，从 15:00到16：00也是1小时，所以是2小 时。 拨钟面：14：00就是下午2时，出示2时 钟面，时针走了一大隔，指着3，这时是几 时（15时），时针又走了一大隔，指着4， 也就是16时。时针共走过几大隔（2大隔）， 也就是过了2小时。 计算：教师根据学生回答板书计算的过程。 (16-14=2(小时)) （3）教师小结：你们看，“六一剧场”开 始的时刻和结束的时刻都正好是整时的，所 以我们还可以用结束的时刻减去开始的时 刻来计算播出的时间。 根据学生回答，随 机板书节目名称、 开始的时刻、结束 的时刻等。 及时肯定学生的方 法，激励学生用多 种方法去解决问 题。 把学生的 注意力集 中起来， 情绪调动 起来。 让学生把 自己的想 法与同学 交流，然 学生多种 方法去思 考问题。 学生体验 时间流逝 的过程 让学生对 于此类问 题有比较 清楚的认 识，也为 后面解决 问题做铺 垫。
断裂力学答案
（ （ = K I + K I(2) 1.简述断裂力学的发展历程（含 3-5 个关键人物和主要贡献）。 答： 1）断裂力学的思想是由 Griffith 在 1920 年提出的。他首先提出将强度与裂纹长度定量 地联系在一起。他对玻璃平板进行了大量的实验研究工作，提出了能量理论思想。（2）断裂 力学作为一门科学，是从 1948 年开始的。这一年 Irwin 发表了他的第一篇经典文章“Fracture Dynamic （断裂动力学）”，研究了金属的断裂问题。这篇文章标志着断裂力学的诞生。（3） 关于脆性断裂理论的重大突破仍归功于 Irwin 。他于 1957 年提出了应力强度因子的概念，在 此基础上形成了断裂韧性的概念，并建立起测量材料断裂韧性的实验技术。这样，作为断裂 力学的最初分支——线弹性断裂力学就开始建立起来了。（4）1963 年，Wells 提出了裂纹张 开位移（COD ）的概念，并用于大范围屈服的情况。研究表明，在小范围屈服情况下 COD 法与 LEFM 是等效的。（5）1968 年，Rice 等人根据与路径无关的回路积分，提出了 J 积分 的概念。J 积分是一个定义明确、理论严密的应力应变参量，它的实验测定也比较简单可靠。 J 积分的提出，标志着弹塑性断裂力学基本框架形成。 2.断裂力学的定义，研究对象和主要任务。 答： 1）断裂力学的定义：断裂力学是一门工程学科，它定量地研究承载结构由于所含有的 一条主裂纹发生扩展而产生失效的条件。 （2）研究对象：断裂力学的研究对象是带有裂纹的承载结构。 （3）主要任务：研究裂纹尖端附近应力应变分布，掌握裂纹在载荷作用下的扩展规律；了 解带裂纹构件的承载能力，进而提出抗断设计的方法，保证构件安全工作。 3.什么是平面应力和平面应变状态，二者有什么特点？请举例说明之。 答：（1）平面应力：薄板问题，只有 xoy 平面内的三个应力分量σ x 、σ y 、τ xy ； ε z ≠ 0 ， 属三向应变状态。 （2）平面应变：长坝问题，与 oz 轴垂直的各横截面相同，载荷垂直于 z 轴且沿 z 轴方向无 变化； ε z = 0 ， σ z ≠ 0 ，属三向应力状态；材料不易发生塑性变形，更具危险。 4.什么是应力强度因子的叠加原理，并证明之。掌握工程应用的方法。 答：（1）应力强度因子的叠加原理：复杂载荷下的应力强度因子等于各单个载荷的应力强 度因子之和。 (1) 在外载荷 T 2 作用下，裂纹前端应力场为 σ2，则相应的应力强度因子为 K I(2) = σ 2 π a 如果外载荷 T 1 和 T 2 联合作用，则裂纹前端应力场为 σ1+ σ2 ，则相应的应力强度因子为 K I = (σ 1 + σ 2 ) π a = σ 1 π a + σ 2 π a (1) 6.为什么裂纹尖端会发生应力松弛？如何对应力强度因子进行修正？ 答：裂纹尖端附近存在着小范围的塑性区（设塑性区是以裂纹尖端为圆心，半径为 r0 的圆 π a 形区域），材料屈服后，多出来的应力将要松驰（即传递给 r>r0 的区域），使 r0 前方局部地 区的应力升高，又导致这些地方发生屈服。即屈服导致应力松弛。 Irwin 提出了有效裂纹尺寸的概念 a eff = a + r y 对应力强度因子进行修正，在小范围条件下，
计算复杂性理论031104(2)
第三章计算复杂性理论主要内容 3.1 Turing机 3.2 计算复杂性理论 3.3 NP完全性理论的基本概念 3.4 NP完全性证明 3.5 用NP完全性理论分析问题 3.6 NP难度
3.1 Turing机 一、Turing机的定义 1. 基本模型 2. 基本Turing机的变种 单向带的Turing机 k条带的Turing机 非确定型的Turing机 二、Turing机模型的等价性 1. 单向带Turing机与基本Turing机等价 2. k条带的Turing机与基本Turing机等价 3. 非确定型Turing机与基本Turing机等价
一、Turing机的定义 1. 基本模型 双向无限带的Turing机M =
(ID) α1qα 2 表示此刻Turing机的FSC处于状态q,读写头 指在串α 2 的第一个字符. 例如Turing机M的某时刻的状态转移函数是 δ(q,x i ) = (p,Y,L) 带上的字符串为x 1x 2 ...x i ...x n , 读写头指向字符x i , 则 它的瞬间描述是: x 1x 2 ...x i-1 qx i ...x n ┣x1x2...x i-2px i-1Yx i+1...x n ┣表示由左边的ID一步达到右边的ID ┣*表示由左边的ID经有限步达到右边的ID
Ansys 断裂力学理论
第四章断裂力学 文献来源：https://www.wendangku.net/doc/473474377.html,/document/200707/article796_2.htm 4.1 断裂力学的定义 在许多结构和零部件中存在的裂纹和缺陷，有时会导致灾难性的后果。断裂力学在工程领域的应用就是要解决裂纹和缺陷的扩展问题。 断裂力学是研究载荷作用下结构中的裂纹是怎样扩展的，并对有关的裂纹扩展和断裂失效用实验的结果进行预测。它是通过计算裂纹区域和破坏结构的断裂参数来预测的，如应力强度因子，它能估算裂纹扩展速率。一般情况下，裂纹的扩展是随着作用在构件上的循环载荷次数而增加的。如飞机机舱中的裂纹扩展，它与机舱加压及减压有关。此外，环境条件，如温度、或大范围的辐射都能影响材料的断裂特性。 典型的断裂参数有： 与三种基本断裂模型相关的应力强度因子(K I,K II,K III)(见图4-1)； J积分，它定义为与积分路径无关的线积分，用于度量裂纹尖端附近奇异应力与应变的强度； 能量释放率(G)，它反映裂纹张开或闭合时功的大小； 注意--在本节大部分的图形中裂纹的宽度被放大了许多倍。 图4-1 裂缝的三种基本模型 4.2 断裂力学的求解 求解断裂力学问题的步骤为：先进行线弹性分析或弹塑性静力分析，然后用特殊的后处理命令、或宏命令计算所需的断裂参数。本章我们集中讨论下列两个主要的处理过程。 裂纹区域的模拟； 计算断裂参数。 4.2.1 裂纹区域的模拟 在断裂模型中最重要的区域，是围绕裂纹边缘的部位。裂纹的边缘，在2D模型中称为裂纹尖端，在3D模型中称为裂纹前缘。如图4-2所示。
图4-2 裂纹尖端和裂纹前缘 在线弹性问题中，在裂纹尖端附近(或裂纹前缘)某点的位移随而变化，γ是裂纹尖端到该点的距离，裂纹尖端处的应力与应变是奇异的，随1/变化。为选取应变奇异点， 相应的裂纹面需与它一致，围绕裂纹顶点的有限元单元应该是二次奇异单元，其中节点放到1/4边处。图4-3表示2-D和3-D模型的奇异单元。 图4-3 2-D和3-D模型的奇异单元 4.2.1.1 2-D断裂模型 对2D断裂模型推荐采用PLANE2单元，其为六节点三角形单元。围绕裂纹尖端的第一行单元，必须具有奇异性，如图4-3a所示。PREP7 中KSCON命令(Main Menu>Preprocessor>-Meshing-Shape & Size>-Concentrat KPs-Create)用于指定关键点周围的单元大小，它特别适用于断裂模型。本命令自动围绕指定的关键点产生奇异单元。命令的其他选项可以控制第一行单元的半径，以及控制周围的单元数目等，图4-4显示用KSCON命令产生的断裂模型。
计算简单的经过时间教案
简单的经过时间计算 一、教学目标 （一）知识与技能初步理解时间和时刻的意义，会计算简单的经过时间，加深学生对24时计时法的认识。 （二）过程与方法在自主探究计算简单的经过时间过程中，初步掌握一些求简单的经过时间的方法，进一步发展学生的推理能力和解决问题的能力。 （三）情感态度和价值观体会简单的时间计算在生活中的应用，建立时间观念，体会合理安排时间的重要性，养成珍惜时间的良好好习惯。 二、教学重难点 教学重点：会计算简单的经过时间，加深学生对24时计时法的认识。 教学难点：理解计算经过时间方法的原理。 三、教学准备课件 四、教学过程 （一）复习导入 用24时计时法表示下面的时刻。 晚上11时（）时中午12时（）时 上午8时（）时下午3时（）时 指名回答，并说说怎么把12时计时法转化为24时计时法。 （二）创设情境，提出问题 课件出示情境图： 教师：从情境图中，你了解了哪些信息？ 学生汇报交流。（其中的下午6点是什么时候的下午6点？） 教师：根据信息你能提出数学问题吗？ 预设：到奶奶家要坐多长时间的火车？ 教师：这个问题怎么解决呢？那么先请大家思考：什么是时刻，什么是时间？ 同桌互相交流并汇报。 小结：“时刻”表示一天内某一特定的时间点。钟面上时针和分针所指的每一个位置都表示时刻。“时间”表示从某一个时刻到另一个时刻的间隔，就是经过的时间。 这就是这节课我们要学习的简单的经过时间计算。（板书：简单的经过时间计算）（三）自主探究，寻找策略 1．学生独立思考，寻找解决问题的办法。 教师：解决这个问题，你有什么好办法吗？ 2．小组讨论交流。 教师：和同学说一说你是用什么办法解决问题的。 3．请各小组派代表向全班汇报展示解决的方法。 （1）在钟面上数一数的方法，数出到奶奶家要坐9小时的火车。（操作演示） （2）利用普通计时法分段计算。 先求出上午坐火车的时间，再加上下午坐火车的时间。 即：12时－9时＝3（小时），3时＋6时＝9（小时）。 结合学生的汇报教师出示“时间轴”进行演示。 （3）运用24时计时法计算。 将下午6时用24时计时法表示，用结束的时刻减开始的时刻，就等于经过的时间。 下午6时是18︰00，18时－9时＝9（小时）。 结合学生的汇报教师出示“时间轴”进行演示。
人教版数学三年级下册6.2《计算简单的经过时间》教案
《计算简单的经过时间》 一、教学目标 （一）知识与技能 初步理解时间和时刻的意义，会计算简单的经过时间，加深学生对24时计时法的认识。 （二）过程与方法 在自主探究计算简单的经过时间过程中，初步掌握一些求简单的经过时间的方法，进一步发展学生的推理能力和解决问题的能力。 （三）情感态度和价值观 体会简单的时间计算在生活中的应用，建立时间观念，体会合理安排时间的重要性，养成珍惜时间的良好好习惯。 二、教学重难点 教学重点：会计算简单的经过时间，加深学生对24时计时法的认识。 教学难点：理解计算经过时间方法的原理。 三、教学准备 课件、钟面。 四、教学过程 （一）创设情境，提出问题 课件出示情境图： 教师：从情境图中，你了解了哪些信息？ 学生汇报交流。 教师：根据信息你能提出数学问题吗？ 预设：到奶奶家要坐多长时间的火车？
教师：这个问题怎么解决呢？这就是这节课我们要学习的计算简单的经过时间。 （板书：计算简单的经过时间） （二）自主探究，寻找策略 1．学生独立思考，寻找解决问题的办法。 教师：解决这个问题，你有什么好办法吗？ 2．小组讨论交流。 教师：和同学说一说你是用什么办法解决问题的。 3．全班汇报。 请各小组派代表向全班汇报。 预设： （1）在钟面上通过拨针的方法，数出到奶奶家要坐9小时的火车。（操作演示） （2）利用普通计时法分段计算。先求出上午坐火车的时间，再加上下午坐火车的时间。即：12－9＝3（小时），3＋6＝9（小时）。 结合学生的汇报教师出示“时间轴”进行演示。 （3）运用24时计时法计算。将下午6时用24时计时法表示，用结束的时刻减开始的时刻，就等于经过的时间。下午6时是18︰00，18－9＝9（小时）。 结合学生的汇报教师出示“时间轴”进行演示。
计算理论知识点
1.如果一个语言被有穷自动机识别，则这个语 言是正则语言。 2.正则语言在并运算、连结、星号运算下封闭 3.每一台非确定有穷自动机都等价与一台确 定型有穷自动机。 4.一个语言是正则的当且仅当有一台非确定 型有穷自动机识别。 5.空集连接到任何集合上得到空集，空串连接 到任何一个串上不改变这个字符串。 6.一个语言是正则的，当且仅当有一个正则表 达式描述。 7.如果一个语言是正则的，则可以用正则表达 式描述它。 8.任何一个上下文无关语言都可以用乔姆斯 基范式的上下文无关文法产生。 9.一个语言是上下文无关的当且仅当存在一 台下推自动机识别它。 10.如果一个语言被下推自动机识别，则它是上 下文无关的。 11.每一个正则语言都是上下文无关的。 1.格局——图灵机计算过程中，当前状态、当 前带内容和读写头当前的位置组合在一起， 称为图灵机的格局。 2.图灵可识别（递归可枚举语言）——如果一 个语言可能被某一图灵机识别，则称该语言 是图灵可识别的。 3.图灵可判定（递归语言）——如果一个语言 能被某一图灵机判定，则称它是一个图灵可 判定的。 ——在输入上运行一个TM时，可能出现三种结果：接受、拒绝或者循环。这里循环仅仅指机器不停机，而不一定是这个词所指的那样，永远以同样的方式重复同样的步骤。 ——图灵机有两种方式不接受：一种是它进入拒绝状态而拒绝它，另一种是进入循环。 4.判定器——有时候很难区分进入循环还是 需要耗费很长时间的运行，因此，我们更喜 欢讨论所有输入都停机的图灵机，他们永远 不循环，这种机器称为判定器。他们总是能 决定接受还是拒绝，也称识别某个语言的判 定器判定该语言。 5.每一个可判定语言都是图灵可识别的。 6.每一个多带图灵机等价于一个单带图灵机。 7.非确定型图灵机都等价于一个确定型图灵 机。8.如果一个语言是图灵可识别的，当且仅当存 在非确定型图灵机识别它。 9.一个语言是图灵可判定的，当且仅当存在非 确定型图灵机判定它。 10.丘奇图灵论题——算法的明确定义。 11.详细描述图灵机的术语——①形式化描述， 详尽的写出图灵机的状态、转移函数，这是 最底层次的、最详细程度的描述。②描述水 平要高一些，称为实现描述，使用日常用语 来描述图灵机，没有给出状态和转移函数③ 高水平描述，他也是使用日常用语来描述算 法，忽略了实现模型不需要提及图灵机怎样 管理它的带子和读写头。 12.A DFA（确定型有穷自动机）、A NFA（非确定 型有穷自动机）、A REX（正则表达式）、 E DFA（判Φ的确定型有穷自动机）、EQ DFA（两 个判别同一个语言的DFA）、 A CFG（上下文无关文法）、ＥCFG（判Φ上下文 无关文法）、 A LBA（线性界限自动机）、是一个可判定语言 每一个上下文无关语言是可判定的。 A TM（图灵机）、停机问题、HALT TM（一个图 灵机对于给定的输入是否停机）、E TM（不接受任 何语言图灵机）、REGULAR TM（正则图灵机）、 EQ TM（接受串相等的图灵机）、 E LBA（不接受语言的线性界限自动机）、 ALL CFG、PCP（波斯地图对应实例）是不可判定 的。 A TM（补）是不可识别的。 13.一个语言的补是由不在此语言中的所有串 构成的语言。如果一个语言的补集是图灵可 识别的语言，则称它是补图灵可识别的。 14.一个语言是可判定的，当且仅当它既是图灵 可识别的，也是补图灵可识别的。 15.设M是一个图灵机，w是一个串。M在w 上的一个接受计算历史（accepting computation history）是一个格局序列C1、 C2、……、C l，其中C1是M在w上的起始 格局，C l是M的一个接受格局，且每个C i 都是C i-1的结果，即符合M规则。M在w 上的一个拒绝计算历史可类似定义。只是 C l是一个拒绝格局。 16.计算历史都是有限序列。如果M在w上永 不停机，则在M上既没有接受历史，也没 有拒绝计算历史存在。确定型机器在任何给 定的输入上最多只有一个计算历史。非确定 型机器即使在单个输入上都有多个计算历 史，他们与各个分支相对应。 17.线性有穷自动机是一种受到限制的图灵机， 它不允许其读写头离开包含输入带的区域。 如果此机器试图将它的读写头离开输入的 两个端点，则读写头就在原地保持不动。这 与普通的图灵机读写头不会离开带子的左 端点方式一样。 18.讲一个问题归约为另一个问题的概念可以 用多种方式来定义，选择哪种方式要根据具 体应用的情况。我们选择一种简单方式的可 归约性，叫做映射可归约性。 19.用映射可归约性把问题A归约为问题B指 的是：存在一个可计算函数，他将问题A 的实例转换成问题B的实例。如果有了这样 一个转换函数（称为归约），就能用B的解 决方案来解决A。 20.函数f：∑*→∑*是一个可计算函数，如果 有某个图灵机M，使得每个输入w上M停 机，且此时只有f(w)出现在带上。 21.语言Ａ是映射可归约到语言Ｂ的，如果存在 可计算函数f：∑*→∑*使得对每个ｗ ｗ∈Ａ<=>f(w)∈Ｂ 22.记做Ａ≤ｍＢ，称作函数ｆ为Ａ到Ｂ的归约。 如果Ａ≤ｍＢ且Ａ是不可判定的，则Ｂ也是不 可判定的。 如果Ａ≤ｍＢ且Ｂ是图灵可识别的，则Ａ也是 图灵可识别的 23.EQ TM既不是图灵可识别的，也不是补图灵 可识别的。 24.令ｔ：Ｎ→Ｒ＋是一个函数，定义时间复杂 性类TIME(t(n))为由时间O(t(n))的图灵机可 判定的所有语言的集合。 25.t(n)是一个函数，t(n)≥n。则每一个多带图 灵机都和某一个O(t2(n))时间的单带图灵机 等价。 26.t(n)是一个函数，t(n)≥n。则每一个t(n)时间 的非确定型单带图灵机都与某一个2O(t(n))时 间的确定型单带图灵机等价。 27.P类是一个语言类，该类在多项式时间内可 判定。 28.PATH∈P、RELPRIME∈P、每一个上下文 无关文法都是P 29.一个语言在NP中，当且仅当它能被某个非 确定型多项式时间的图灵机判定。 30.{HAMPATH, CLQUE, SUBSET-SUM, SAT, 3SAT, UHAMPATH, }∈NP 31.P=成员可以快速判定的语言类 NP=成员可以快速验证的语言类 32.若存在多项式时间图灵机M，使得在任何输 入w上，M停机时f(w)恰好在带上，函数f： ∑*→∑*是一个多项式时间可计算函数。 33.语言A称作多项式时间映射可归约到语言 B，或者简称为多项式时间可归约到B，记 为Ａ≤pＢ，若存在多项式时间可计算函数 f：∑*→∑*，对于每一个w，有 ｗ∈Ａ<=>f(w)∈Ｂ 函数f称为A到B的多项式时间归约。 34.列文-库克定理 SAT∈P，当且仅当P=NP 35.3SAT多项式时间可归约到CLIQUE。 36.令f：N→R+是一个函数。空间复杂性类和 NSPACE(f(n))定义如下： SPACE(f(n))={L|L是被O(f(n))空间的确定型 图灵机判定的语言} NSPACE(f(n))={L|L是被O(f(n))空间的非确定 型图灵机判定的语言} 37.萨维奇定理