计祘的相似性与对偶性原理——谈谈理论计祘机科学

电子计算机的发明和发展引起了一场伟大的技术革命,其规模之大,范围之广,变革之深刻,都是人类历史上少有的。比如说,计算机刚发明的时候,人们多半认为它只是用来作计算用的,但是,今天我们已经把它用在文件编     

论计算的相似性与对偶性

一、引言我们有成打的计算模型、多种的计算类型(决定型、非决定型、交错性,…)和多种不同的资源.因此有成百个复杂性的分类和上千个关于各模型之间关系的定理.整个的情况不是很清楚的.所以当前最重要的问题不是去证明一个个孤立的定理,而是去统一整个的理论.从这一     

理论计算机科学中的一些问题

本期发表了两篇关于计算机方面的文章。一篇是关于计算机理论方面的,《理论计算机科学中的一些问题》一文,介绍了作者洪加威同志近年来在这领域中一些根本性的问题上所获得的成果。作者还对计算机科学的发展提出了自己的看法,颇具见地,值得一读。     

复杂度理论中某些不可证明的真命题

在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公     

代数逼近的速度能有多快?

假定我们想要计算任何一个实数,可以从某些整数出发,使用加减乘除开方等运算,并且假定在计算的每一步都可以得到绝对精确的值。那末为了得到n位近似值所需代数运算的步数t(n)或者是O(1),或者是Q(logn),中间的情况不存在。这就是本文的主要结果, 设F(x_1,x_2,…,x_i)是一个关于变元x_1,x_2,…,     

试验批数不限定情现下单因素优选问题的最优策略

自从优选法在国內推广使用以来,关于0.618这一数字的由来及其最优性问题引起了广泛的兴趣. 在单因素优选问题中,经常使用的有黄金分割法(即0.618法)和分数法.分数法在预先限定试验批数情况下的最优性在1953年由Kiefer提出和解决,以后被Wilde等人所发展.但是并不能简单地用取极限     

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

代数逼近的速度能有多快?

本文提出一种例证法,即用计算一个具体的特例来证明几何定理的方法。这个例子只依赖于该几何命题叙述的长度l和自由度s,与命题内容无关,而且很容易给出来。 我们考虑如下一类初等平面几何问题,其中每个命题都由三部分组成。 1.在平面上任选s个点。 2.从这s个点出发,用l个几何作图语句作点作直线或作圆。可以使用的语句有