面向对象数据库系统中类层次及其复杂性研究

从面向对象数据库系统中类层次的基本概念出发，讨论了对象与类的成员关系和类与类之间的交互依赖关系，提出了一种类层次模式描述语言，并讨论了将该语言表达为一阶逻辑的方法．对类层次模式中对象与类以及类与类的关系推理问题的复杂性进行了一些分析     

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

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

并行计算一类奇异方程组的PCR算法

本文给出了一个计算奇异方程组Ｒ（Ａｋ））的新的高度并行算法．通过该算法可以在时间步内，用ｐ＝２ｎ（ｎ－１）台处理机得到方程组的解ｘ＝Ａｄｂ．     

块r－循环矩阵的推广

给出了块初等ｒ－循环矩阵的新概念，研究了之们的性质，证明了利用ＦＦＴ求逆的计算复杂性为Ｏ（ｍ＿２ｎｌｏｇ２ｎ＋ｎｍ￣３）。     

K-n-度

本文基于K-算子提出了K-n-度的概念,得到了NP集类的K-n-度结构的一些初步结果。     

图论算法复杂性问题(一)

本文论述了图论算法复杂性的基本理论和分析方法。由它的表示式和阶的运算,可以分析一个具体问题的算法复杂性,进而明确某一具体算法的有效性。     

最长公共子串的快速搜索算法

本文提出了两个字符串之间最长公共子串这一概念,并在对它进行理论分析的基础上,给出了两种求取最长公共子串的快速算法。     

多项式时间、指数时间复杂性类和Tally集

可计算复杂性类之间的差异和联系是结构复杂性理论中主要研究的问题,而多项式时间复杂性类P和NP与指数时间复杂性类E和NE之间的关系更加引人注目.众所周知:如果P=NP,则E=NE.但反过来是否有:如果E=NE,则P=NP,仍是一个未解决问题.有多种途径试图解决这个问题.Book证明了:E=NE当且仅当在NP-P中不存在Tally集;Hartmanis等证明了:E=NE当且仅当在NP-P中不存在稀疏集(sparse set),这就是著名的向上分离结果(upward-separation result).此外是相对化的应用,到目前为止,关于这个问题     

产生式系统的一种新匹配算法

本文提出了产生式系统的一种新匹配算法，并对新算法的时空复杂性作了估计，还进行了模拟试验，结果表明，新匹配算法明显提高了效率。     

关于相对化多项式界计算的一些结果

本文给出了三个相对化的 P 与 NP 的结果。在 S.Homer 及 W.Maass 的基础上,利用递归论中的优先方法,包括有穷损害优先方法。我们进一步研究相对化的 P 与 NP 问题的结构。比如,证明了存在两个互不可比的 P-禁集。此外,类似于递归中的算术分层及破分性,我们讨论了相对化多项式界计算的有关问题。