IDS-80图形数据库的建立和应用

<正> 前言 从1983到1984,在西德的Aachen、意大利的Florence和法国的Paris等地召开了五次国际数理逻辑和计算机科学软件会议,根据会议动态,数理逻辑与计算机软件相结合在人工智能和数据库管理等方面的发展和应用十分引人注目。为了深入了解计算机的人工智能功能     

关于算法VK2的注

在[1]和[2]中作者们用三值逻辑的方法去计算复布尔函数并且提供了若干个算法.其中的大多数是很快的而且最小化了计算机的存储空间.但是,E.Omerti发现算法VK2的流程图(参看[1])不可能在计算机上实现.事实上为了使用算法VK 2,我们必须翻译复布尔函数为析取范式.但是,容易看出,有时候计算机无法执行这样的翻译.例如,假设我们需要翻译如下的布尔函数为它的析取范式:     

相对化One-Way函数的存在性

One-Way函数在计算复杂性和密码技术中均有重要的应用.将Grollmann和Selman的结果推广到相对化和非一致复杂类的情形,证明了复杂类UP/poly,UP,P/poly等之间的包含关系与强相对化one-way函数、弱相对化one-way函数存在问题的等价性.     

一个计算复杂性问题的讨论(摘要)

根据中国电子学会计算机学会1979年学术活动计划的安排,"计算机科学暑期讨论会"于1979年7月23-30日在吉林省长春市召开。讨论会上宣读的论文共45篇,在此只刊登其中一部分。这些论文生动地反映了我国近几年来计算机科学的研究成果。虽然这还不能全面反映我国计算机科学的研究成果,但从这些论文可以明显地看出,在我国一支小小的计算机科学研究队伍正在形成。这是一棵新生的幼苗,让我们爱护它,培育它。因为在新长征中,它将成长壮大,起到自己应有的作用。     

受限外部信息源计算的P─NP性质

本文对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多项式等价的递归集Ａ，Ｂ，Ａ′，Ｂ″，Ａ″，Ｂ″，Ａ，Ｂ，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ′，ｑ）＝Ｐ（Ａ′），Ｐ（Ｂ′，ｑ）≠Ｐ（Ｂ′）．ＮＰ（Ａ″，ｑ）＝ＮＰ（Ａ″，ｑ＋１），ＮＰ（Ｂ″，ｑ）≠ＮＰ（Ｂ″，ｑ＋１），ＮＰ（Ａ，ｑ）＝ＮＰ（Ａ），ＮＰ（Ｂ，ｑ）≠ＮＰ（Ｂ）．     

用结构性质分开复杂类

ＮＰ是否包含在Ｐ／ｐｏｌｙ中的问题迄今仍为开问题。８０年代初证明了如果ＮＰ∪→Ｐ／ｐｌｙ，则ＰＨ＝∑２，最近，又有了如果ＮＰ∪→Ｐ／ｐｏｌｙ，则ＰＨ＝ＺＰＰ的问题。文中将借助于广义一阶逻辑ζ（ι）及其上的模型论以证明存在ＮＰ中的语言，它们没有多项式大小的线路。     

UP,βn和FewP完全问题的相对同构性

本文引进相对的多项式化归和相对多一多项式同构等概念，对ＵＰ、βｎ的ＦｅｗＰ的相对完全集讨论它们的相对同构问题。并得到如下结果：１（１）对任何≤ｍ＾Ｐ，Ｂｎ－βｎ＾Ｂｎ完全集Ｃ，Ｃ≈Ｐ＾ＢｎＡｎ←→Ｃ为Ｐ＾Ｂｎ柱。（２）对任何≤ｍ＾Ｐ，Ｂ－ＦｅｗＰ＾Ｂ完全集Ｃ，Ｃ≈Ｐ＾Ｂ∪Ａｎ←→Ｃ为Ｐ＾Ｂ柱，其中Ｂ＝ＳＡＴ－∪Ａｎ。 ｎ∈Ｎ ｎ∈Ｎ     

受限外部信息源计算的P—NP性质

本对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多等价的递归集Ａ，Ｂ，Ａ＇，Ｂ＇，Ａ＇＇，Ｂ＇＇，Ａ＇＇＇，Ｂ＇＇＇，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ＇，ｑ）＝Ｐ（Ａ＇），Ｐ（Ｂ＇，ｑ）≠Ｐ（Ｂ＇），ＮＰ（Ａ＇＇，ｑ＋１），ＮＰ（Ｂ＇＇，ｑ）≠ＮＰ（Ｂ＇＇，ｑ＋１），ＮＰ（Ａ＇＇，ｑ）＝ＮＰ（Ａ＇＇），ＮＰ（Ｂ     

公理集合论

众所周知,集合论是数学、计算机科学、哲学等学科的重要理论基础。古典的集合论出现了许多自相矛盾的悖论。近百年来,许多数学家和数理逻辑学家为了克服这些矛盾建立了各种公理化集合论系统。其中尤以二十世纪初问世的Zermelo-Fraenkel(简称ZF)系统和Von Neumann Godel-Bernays(简称BG)系统最为流行。本书作者以极其丰富的材料,全面系统地介绍了ZF系统并扼要地与BG系统作了对照(更详细的介绍,读者可参阅原作者的前言)。为适应我国广大读者日益增长的需要,我们在开设集合论课程的同时将本书译出以供参考。凡我们认为原书有笔误之处均已一一改正并加了按语。限于译者水平,译文不妥之处望读者批评指正。