关于若干函数类的多项式时间谱系(Ⅰ)

对计数函数类#P,Span-P和最优化函数类Opt-P及FΔ₂^P进行了推广,给出了4个关于函数的多项式时间谱系,证明了关于最优化函数的多项式时间谱系,与Krentel定义的谱系是相同的,讨论了这些谱系自身以及谱系之间的关系。     

关于若干函数类的多项式时间谱系(Ⅱ)

研究了4个关于函数的多项式时间谱系,讨论在这些谱系内部以及谱系之间不大可能有的关系,并给出这些函数类的完全问题。     

相对化概率算法类与非确定算法类的强分离

本文提出并讨论了多项式时间概率型算法复杂度语言类与指数时间非确定型算法复杂度语言类的强分离(即带禁集证据的分离)问题,获得并证明了存在一个递归Oracle集A使得在多项式时间有界错误概率复杂度语言类BPP^A中存在NEXT_k^A禁集,这里NEXT_k^A=∪NTIME^A(2^_cnk)表示计算时间限界于O(2^_nk)的指数时间非确定型算法所接受的语言类;我们指出,Oracle集A可以一致地对k构成并列举熟知的语言类P,NP,U,R,BPP,PP,∑₂^p,∏₂^p,Δ₂^p以及交互式证明系统语言类MA,AM,IP等之间的30余种强分离关系作为本文结果的直接推论.     

关于相对Bousfield类和相对Bousfield等价关系

本文研究了有限群的群代数上的有限生成模的相对Bousfield类,定义了相对Bousfield等价关系和相对Bousfield等价类,建立了群与子群的相对Bousfield等价类之间的对应关系.     

限制Witt超代数偶部的可约极大阶化子代数

为了深入研究限制Witt超代数的偶部g在素特征域上的极大阶化子代数,利用g的结构特点构造出g的所有可约极大阶化子代数并给出相应的维数公式.     

核由混合偏导数优控的Fredholm方程类的计算复杂性

解决了以混合偏导数优控的函数为核的第二类Fredholm积分方程类,当2≤p<∞,     

关于相对化的P=?NP问题的注记

问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S₁,S₂,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于P^A=NP^A.     

核属于H函数类的多维Fredholm积分方程类近似解的计算复杂性

给出了在 Lp,2 p<∞ ,范意义下 ,核下自由项均属于 H函数类的多维 Fredholm积分方程类近似解的ε-计算复杂性估计 .     

算子方程近似解直接方法的优化和信息复杂性研究进展

算子方程近似解直接方法的优化和信息复杂性是80年代发展起来的连续复杂性理论的两个主要方面,是计算机科学和数学的交叉研究领域．本文拟就这两个方面的研究进展做一简要介绍．     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

由自共轭线性微分算子所确定的函数类在Lq(T)中的相对宽度

得到了使等式Kn(K2(Pr),MK2(Pr),L2(T))=dn(K2(Pr),L2(T))成立的最小M值,并计算了Kn(K2(Pr),K2(Pr),Lq(T))的渐近阶,其中Kn(.,.,Lq(T))和dn(.,Lq(T)),1≤q≤∞,分别代表Kolmogorov意义下在Lq(T)中的相对宽度和宽度,K2(Pr)表示定义在[-π,π]上由自共轭线性微分算子所确定的光滑函数类.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.     

关于定积分概念的数列化

讨论定积分概念的数列化及其相关问题．使用经典的精确分析方法,得到一个数列化的可积的充要条件．探索微元法表述后续相关概念与证明相关结果．同时举例说明定积分概念数列化的优越性与微元法处理后续相关问题的可行性．     

一秩扰动下算子的定化性

本文对于Krein空间上的强可定化算子(一致可定化箅子)在使扰动前后预解式之差为一秩算子的扰动下,强可定化性,一致可定化性是否成立的问题进行了讨论.得到了使扰动之后的算子保持强可定化性(一致可定化性)的条件.     

Banach空间中非光滑算子方程的光滑化拟牛顿法

研究Banach空间中非光滑算子方程的光滑化拟牛顿法.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化拟牛顿法具有局部超线性收敛性质.应用说明了算法的有效性.     

Krein空间上算子的可定化性

从Hilbert空间(H,(·,·))上的一个有界自伴算子G可以导出不定内积[·,·]=(G·,·),本文给出了由G所导出的Krein空间上的G-自伴、G-酉以及G-正常算子的可定化、强可定化和一致可定化性质以及这三种不同的可定化性之间的关系.     

近似超紧空间的相对可乘性

利用广义Zadeh型函数讨论近似超紧性的相对可乘性问题,使得文[1]与[3]的一些结果是本文的推论。     

线性分式规划问题的多项式时间近似算法

本文针对线性比式和分式规划问题,提出一种求其全局最优解的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.     

Hom-可计算余代数的局部化

本文研究了可计算余模和Hom-可计算余代数的局部化问题.利用局部化方法,得到了可计算余模和Hom-可计算余代数的等价条件,推广了余代数上局部化理论的发展.     

关于广义Sublaplacian算子特征函数的展开

本文研究了广义Ｓｕｂｌａｐｌａｃｉａｎ算子特征函数的展开．通过定义广义　－扭曲卷积，我们得到相应的Ｐｌａｎｃｈｅｒｅｌ定理及Ｈａｕｓｄｏｒｆｆ－Ｙｏｕｎｇ不等式，最后，我们还给出了当广义Ｓｕｂｌａｐｌａｃｉａｎ算子的特征值为离散时的一些结果．