MU(1)内公式改名的多项式可判定性

研究判定合取范式公式F和H之间是否存在一个改名φ使得φ(F)＝H的计算复杂性。公式的改名是将命题变元映到变元本身或变无的否定的一个映射，对于极小不可满足公式的子类射MU／(1)中的公式，我们证明了其改名判定问题在多项式时间内是可判定的。     

MXX和MARG中公式改名的复杂性

研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．     

一个极小不可满足公式子类的等价结构

研究一个极小不可满足公式子类（MAX（1）的等价结构,考虑了MAX（1）上的变元改名问题和文字改名问题。此两个问题均可在O（nlog2(n))时间内可解。     

可满足公式到极小不可满足公式MU(1)的扩张复杂性

可满足合取范式（CNF）公式F到极小不可满足公式MU（1）的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var（G）包含var（F）并使得F＋G∈MU（1）。Horn公式到MU（1）公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解决。这里我们将给出一个多项式时间的算法解决这一问题。     

NT-HIT(k)公式的存在性

一个合取范式(CNF)公式F是NT-HIT公式,如果F中的任意两个不同的子句中恰有一对互补文字。NT-HIT(k)是公式的子句数与变元数之差为k的NT-HIT公式类。通过构造一个命题公式Hn,m,我们证明了：(1)Hn,m可满足当且仅当存在一个含有n个变元和m个子句的NT-HIT公式。(2)对于NT-HIT(1)中的任意一个公式F,存在一个文字L,L在F中仅出现一次。进一步,我们证明了：对于k≥2,公式Hn,n k是一个不可满足公式。于是,对于k≥2,NT-HIT(k)是一个空集。从而就解决了[1]中的两个公开的问题。     

MARG-MU(2)的结构和复杂度

SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向.本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的结构和复杂度:在结构方面,MARG-MU(2)中的公式要么是F22,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU(2)对(1,*)-消解封闭,则某个含有n个变元和n+2个子句的公式是否为MARG-MU(2)中的公式的问题可以在时间0(n3)内被判定.     

MARG-MU（2）的结构和复杂度

SAT问题（可满足性问题）是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向。本文主要利用（1,＊）-消解方法研究了差为2的边缘极小不可满足公式集（MARG-MU（（2））的结构和复杂度：在结构方面,胁MARG—MU（2）中的公式要么是F2^2,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU（2）对（1,＊）-消解封闭,则某个含有,1个变元和n＋2个子旬的公式是否为MARG-MU（2）中的公式的问题可以在时间O（n^3）内被判定。     

Fubini定理公式数计数和φ(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fubini定理公式数无显式公式,本文利用完全图Kn的k个分支的完全分支覆盖的个数N(Kn,k)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fubini定理的公式数的显式公式,此外获得完全I-部图所有个数基数公式,本文中提出φ(n,k)概念,并讨论φ(n,k)的组合卷积公式,最后证明φ(n)=∑nk=1φ(n,k)与Fubini公式数之间的关系等式.     

Fubini定理公式数计数和齘(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fubini定理公式数无显式公式,本文利用完全图Kn 的k 个分支的完全分支覆盖的个数N(Kn,k)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fubini定理的公式数的显式公式,此外获得完全i 部图所有个数基数公式,本文中提出(n,k)概念,并讨论(n,k)的组合卷积公式,最后证明(n)=∑nk=1(n,k)与Fubini公式数之间的关系等式.     

(s,k)-较多序类和多目标规划的(s,k)-较多有效性

引进有限维向量空间的(s,k)-较多序类概念,　并给出它们的基本性质.　在此基础上,定义了多目标规划问题的(s,k)-较多有效解和(s,k)-较多最优解,　研究了它们之间的关系,　以及它们与Pareto有效解、Pareto弱有效解、较多有效解和较多最优解等的关系.     

多项式（1＋x）^k＋（1-x）^k-2^k的整除性问题

对于整数k,设Tn（x）=（1＋x）^k＋（1-x）^k-2^k,设m,n为正整数,且m4,均有T4（x）不整除Tn（x）.     

求解P*(k)阵线性互补问题的内点幂级数算法

本对P*(k)阵线性互补问题,给出了一种内点幂级数算法,其迭代复杂度为O（2k 1)^2n^(1 1/r)/2L^(1 1)/r,r为阶数。     

k阶伴随矩阵C*k(AB)的性质

对于给定的数域F上的n阶矩阵A,给出并证明了k阶子式阵Ck(AB)的伴随矩阵C*k(AB)的一个性质:C*k(AB)=C*k(B)C*k(A),从而使一般意义下的伴随矩阵的性质(AB)*=(B)*(A)*得到推广.     

求解k(<10)-中心问题的快速算法

提出求解3-中心问题、4-中心问题、5-中心问题及k(<10)-中心问题的算法.设计该算法的依据是覆盖点集的凸壳必覆盖点集.算法首先判定点集凸壳的形状,然后确定k个圆的排列方式,最后以确定方式计算圆心位置.证明了算法的正确性并且分析了算法的复杂性.     

（k，k-1）-双正则图的平衡Judicious Partitions

Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobds和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1).双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.     

具2+δ阶矩的一类时变MAX(q)序列的样本均值的极限分布

本文继续作者在文献[1]中的工作,证明具2+δ(0<δ<1)阶原点矩的时变 MAX(q)序列{x_n)的样本均值 N~(1/2)(_N-E_N)渐近正态分布 N(0,ν_2-ν_2-(2q+1)μ~2),其中μ_1=Ex_1,ν_2=E(x_1+x_2+…+x_(q+1))~2,ν_2=E(x_1+x_2+…+x_q)~2,从而,减弱了文献[1]中要求{x_n}具有限三阶原点的限制条件.但其论证方法与文献[1]不相同.