递归集的K-1-度上半格的格嵌入性

本文研究了递归集的K-1-度上半格的格嵌入性,证明了任一可数分配格及任一可数偏序集均可嵌入〈R_K~1(NP_K~1);≤〉的任一区间.     

复杂性集类中的完全集问题

本文针对多项式时间多一归约、图灵归约及强图灵归约,探讨了一些复杂性集类存在完全集的充要条件,指出了此三种归约有表现在完全集上的差别.     

复杂性集类的递归论结构

本文使用间隙语言方法研究了复杂性集类的递归论结构,得到了复杂性集类集合剖分的许多新结果。     

关于一些多项式时间度对的连续性

本文的主要结果是:对任何度,存在使并且对任何度。     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

A Potential-Reduction Algorithm for Linear Complementarity Problems

Feasible-interior-point algorithms start from a strictly feasible interior point,but infeassible-interior-point algorithms just need to start from an arbitrary positive point.we give a potential reduction algorithm from an infeasible-starting-point for a class of non-monotone linear complementarity problem.Its polynomial complexity is analyzed.After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region.     

一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

关于图同构复杂性的一点补充

在图G=(V，E)中，删除其度数最大的顶点及其关联的边，在余下的子图中，如法炮制，直至余下的子图为零图．设所删除的这些顶点x1，x2，…，xi的度数依次为P1，P2，…，Pl，称序列P1，P2，…，Pl为图G的度序列；xi(1≤i≤l)关联的边的另一端点在G中的度数的集合称为顶点五关联的度集合．通过计算、比较两图的度序列、被删除的顶点的度数以及它们关联的度集合，证明两图同构问题的复杂度是多项式的．     

算法的时间复杂度分析

算法的时间复杂度是衡量一个算法优劣的重要指标.在总结教学经验的基础上,提出了几种计算时间复杂度的方法.     

中国剩余定理在多项式乘法计算中的应用

本文首先给出了一个有效的中国剩余定理,然后给出一个应用该定理的具有大整数系数的多项式乘法算法,并对该算法的运行时间进行了分析。     

线性规划的Karmarkar方法(续)

线性规划的多项式算法——Karmarkar方法，是近期国际运筹学界的著名成果，它在理论与实用上都有重要意义，本文希望用比较通俗的方式介绍它，以便让更多的人们了解这一方法并将它应用于实际，产生更多的经济效益。     

可变费用的单机等待损失排序问题

证明了可变费用的单机等待损失排序问题１‖Σｆ＿ｉ（ｃ＿ｉ）是ＮＰ－ｈａｒｄ；给出了一般情形下工件优先安排加工的两个判别条件；对几种特殊情形给出了多项式时间算法或最优解的判定条件。     

H_n~′中的多项式极性和系数估值

有关H_n′中的多项式的极性和系数估计的一些结果,即是本文第三部分中之定理4～定理6。这些结果在所著之“函数构造论”中,证而不严,或只提而不证(并非显然的结果)。本文首先证明在H_n′中,在[-1,1]上与“0”最小偏差的多项式之唯一性定理,并通过建立多项式的显式加以变形,然后论证它们。     

一类新图族及其分类

本文按递归构造法给出了一类新图族，研究了其伴随多项式第四项系数的规律，由此得到了一种分类方法，其结果有助于我们进一步研究此类图族补图的色唯一性及色等价划分。     

一类带有参数的线性拟周期微分方程系统的可约化性

考虑一类带有参数的拟周期系数线性微分方程系统.x=(A(ξ) Q(t,ξ))x,x∈Rn的可约化性问题,其中ξ为参数,A(ξ)是常系数矩阵,Q(t,ξ)是依赖于ξ的拟周期矩阵.设拟周期矩阵Q(t,ξ)的频率关于参数ξ满足Rüssmann非退化条件,且与A(ξ)的特征值满足一定的非共振条件.证明了当Q(t,ξ)充分小时,在测度意义下对大多数的ξ,微分方程系统是可约化的.