一致与非一致复杂类的模型论性质

自从1965年J.Edmonds和A.Cobham提出P-NP问题以来已有30年的研究历史。目前环绕这个问题的大量学术论文和研究专著已使它发展成为计算机科学中最新和最活跃的研究领域之一,近年来,人们除了对由各种类型的图灵机确定的复杂类(如P,NP,PSPACE等)进行研究外,对一些用其他方法定义的非一致复杂类(如P/poly,P/log,NP/poly等)也越来越有兴趣,而且许     

紧致性定理的纯语义证明

紧致性是一阶模型论的重要性质之一,本文给出紧致性定理的一个比较完整的纯语义证明。     

UP,βn和Fewp的相对可分离性

本文给出ＵＰ、βｎ和ＦｅｗＰ与ＮＰ和ＰＳＰＡＣＥ相对于Ｔａｌｌｙ集的分离结果。同时还引入强ｎ－范畴机和强ｐ－范畴机等概念，并比较它们所接受的语言类在Ｐ－ＮＰ情况下的性质，得到如下结果；存在递归ｏｒａｃｌｅＡ和Ｂ，以及递归Ｔａｌｌｙ集Ｔ和Ｔ＾１，使得：（１）Ｐ＾Ａ－β＾Ａｎ且Ｐ＾ＡＲ≠β＾ＡＮ，（２）Ｐ＾Ｂ＝ＦｅｗＰ＾Ｂ     

基于IDS 80图形系统的液压和气动设备符号库

我们在此给出一个在意大利IDS—80图形计算机系统上实观的符号库。我们扼要地概述了该库的构造和使用方法。这个库是一个遵循机械设计统一标准UNI的标准符号库并且我们的方法(模型扩张)是新的和有价值的。     

ND—7301编译系统(Ⅰ):初始语言

本文扼要介绍了 ND-7301编译系统中所用的初始语言。全文共分六节。第一节是引言,其中谈到这种语言的设计背景,设计目标,以及语言的结构。第二节是基本符号、数、名、量、值。第三节是公式和子句。第四节是说明。第五节是程序、模块、注解等。第六节给出了两个例子。本语言是一种既可用来写应用程序又可用来写系统程序的语言。在模块参数以及子句等部分还考虑了一些利于动态调试的成分。     

奇异Ulam集的判定

如果允许 1次说谎的 Ulam 集 U~(1)=(x_1,x_0)为 n 可解,则恒有x_1(n 1) x_0≤2~n(见[3]命题3(ii)).现设 U~(1)的解为 k,又设 l=min(x_1(n 1) x_0≤2~n),本文证明,k=l 当且仅当 x_1为奇数且 x_0相似文献   

一个判定算法的研究

本文致力于相容结构的可判定性的证明并给出了一个快速的判定算法。