基于1RSB的正则(k,r)-SAT问题可满足临界

针对每个变元恰好出现r次且其正、负出现各为r/2次的随机正则(k,r)-SAT问题,结合一阶复本对称破缺理论和随机正则(k,r)-CNF公式解空间的几何结构,分析了通常以解的总数作为一阶矩方法的随机变量时,所得到的随机正则(k,r)-SAT问题可满足临界值上界偏大的本质原因.在此基础上,通过计算可满足相变点附近区域中随机正则(k,r)-CNF公式的解的聚类总数,从而把计算其解的规模转换为计算其解的聚类规模.进一步,通过引入覆盖的定义来表示聚类,并以覆盖总数作为一阶矩方法中的随机变量,结合相关的概率分析,得到了当前该问题可满足临界值点的一个新上界,使得上、下界之间仅有常数1的间隙.     

一些简化的NP完全实例类

(k，s)-SAT是命题满足性问题限制在一种特殊的命题公式上，该命题公式具有每个子句只有k个不同的文字且每个变元出现的次数少于s次的特点。已经验明对于正整数k，s存在一个指数函数f，满足：对任意s≤f(后)，所有的(k，s)-SAT例都是可满足的，而(k,f(k)-SAT却是一个NP-完全问题。目前为止，只知道f(3)和f(4)的精确值．对于，是否可计算是一个仍未解决的问题．由于每个满足某种条件的数值序列对应一个MU(1)中的公式，在[2]中，作者S．Horry和S．Seizder通过对数值序列的运算来构造(k，s)-SAT中的MU(1)公式例，得到了函数厂的可计算上界函数。但当k比较大时，该方法不太实用。作者定义了一种树规则来减少数值计算的步数，得到了一个确定的实用的算法来计算函数f的上界，该上界接近[2]中的上界，同时，也得到了一些NP-完全满足性问题类。     

随机k-SAT的相变上下界

在随机k-SAT模型的基础上,针对合取范式的满足性问题进行研究。对于固定的变量数n,随着子句数m增加,当m/n接近某一值时公式的可满足性发生剧烈的变化,可满足的概率从1变为0,也就是经常提到的相变问题。证明k-SAT相变的阈值上界为2kln2;当k(k53)比较小时阈值下界为2~(k-1)ln2;当k(k≥53)比较大的时候,对任何ε=ε(k)0(ε是关于k的函数)且εn→!(趋近无穷大),存在α0=2~k ln2,使得下界为αl=(1-ε)α0。通过实验对k为2,3,4时的阈值进行验证。     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

基于遗传算法求解NPC问题的研究

首先建立了0-1KP问题和3-SAT问题的数学模型;然后分别基于遗传算法（GA）与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT问题的可行算法;最后通过对0-1KP实例和3-SAT实例的仿真计算验证了算法的可行性与有效性。     

有界域中的微分算子和正则半群

设Ω Rn是一个有界区域.如果P(ξ)是一个2m次实系数椭圆多项式,利用Sobolev嵌入定理和正则半群的内插定理,证明了当k≥n/2m|1/2-1/p|(1＜p＜∞)时 p(具有Dirichlet边界条件)在Lp(Ω)中,当k＞n/4m(k∈N0)时 1在L1(Ω)中, ∞在L∞(Ω)中, 0在C0(Ω)中和 c在C( )中生成一个(1-△p)-km-正则群.结果表明在有界区域中偏微分算子比在Rn中具有更好的正则性.     

有限域上的华林问题

设g(k ,pn) =min{s:对任意的a∈Fpn,存在x1…xs,使得a =xk1+… +xks}如果g(k ,pn)存在 ,那么g(k ,pn) (1+ [2lnpnln2 ])n[(2k) 1/n](当pn2 >k时 ) .     

s个几乎相等的素数的k次方和(Ⅱ)

假定 pθ‖ k,当 p =2 ,2 |k时 ,γ =θ +2 ;其他情况时 ,γ =θ +1。而 R = ( p-1) | kpγ。在GRH(广义 Riemann假设 )下 ,证明了当 s≥ 2 k2 (2 logk +log logk +2 .5 ) ,k >1 1时 ,任何足够大的整数 N≡ s(mod R)都可以表示为 s个几乎相等的素数的 k次方和。     

半群Q(k)的极大正则子半带

设T(X)和O(X)分别是X上的全变换半群和保序全变换半群,Y是X的非空子集,令F(X,Y)={α∈T(X):Xα?Yα?Y},OF(X,Y)=O(X)∩F(X,Y).当Y=n≥4时,对任意的2≤k≤n-2,考虑半群Q(k)={α∈OF(X,Y):Im(α)≤k}的极大正则子半带的结构,利用Miller-Clifford定理,证明了半群Q(k)的极大正则子半带有且仅有两类:A(α)=Q(k-1)∪(J(k)\L_α),α∈J(k);B(β)=Q(k-1)∪(J(k)\R_β),β∈N(k).     

一类重特征偏微分方程的可解性

本文讨论了方程■的第二类混合问题及柯西问题的可解性。证明了当c■-(b-a)(k+1)j(j-0,1,…)时,具第二类边界的混合问题有唯一的c解;当c=-(b-a)(k+1)j时,解的存在性、唯一性都失去。给出了解存在的充分必要条件,并证明一类修改问题解的存在唯一性。最后,用延拓的方法讨论了柯西问题的一可解性。