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

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

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

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

关于图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G)|=k的L(2，1)-标号中的最小数k．将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了全图、块图的L(3，2，1)-标号数的上界．     

关于几类图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)|≥1．图G的三(2，1)-标号数λ(G)是使得G有max{f(v)：v∈V(G)}=k的L(2，1)-标号中的最小数k．该文将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了Kneser图、高度不正则图、Halin图的λ3(G)的上界．     

不可满足公式的完备证明系统

合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句。同态映射保持一个公式的不可满足性。一个公式是极小不可满足的是指公式不可满足而且从中删去任一个子句后得到的公式可满足。MU(1)是子句数与变元数的差等于1的极小不可满足公式类。S．Szeider证明了：每个不可满足公式F是MU(1)中某个公式日的同态像。从而，基于MU(1)的同态证明系统与树消解证明系统是p-等价的。MU(1)中的公式可以用基础矩阵表示，本文用基础矩阵的方法证了同态证明系统ПMU（1）的完备性。     

随机均衡正则恰当(2s,k)-SAT问题的可满足相变

为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s?.当ss?时,随机均衡正则恰当(2s,k)...     

具有与(g,f)-因子分解正交的子图

设 ( g(x)和 f(x)是定义在V(G)上的整数值函数 ,且对任意的x∈V(G)有 0 g(x) 相似文献   

亚纯函数及其导数分担两个有限集

1977年，Gross提出了一个问题^[4]：能否找到两个有限集S1，S2，使得对任何满足E（Sj,f)=E(Sj,g)(j=1,2)的两个非常数整函数f(z),g(z)都有f(z)≡g(z)?其中E（S，f)=∪α∈s{E：f(z)-α=0}。对于这个问题，仪洪勋在1994给出了肯定的答案^[5]。至于整函数f(z)及导数f^(k)(z)分担两个有限集的问题，最近方明亮给出了如下结论^[1]。     

两类联图的符号控制数

设图G=(V,E)为一个图,一个双值函数f:V→{1,-1},若S?V,则记f(S)=Σ_(v∈s) f(v).如果对任意的顶点v∈V,均有f(N[v])≥1成立,则称f为图G的一个符号控制函数.图G的符号控制数定义为γ_S(G)=min{f(V) f是图G的一个符号控制函数}.联图G=■∨H是空图■的每个顶点都与图H的每个顶点相连接而成的图.本文主要利用讨论图中-1顶点个数的方法得到下界和用标号法得到上界,从而确定两类联图的符号控制数的精确值,即确定了γ_S(■∨Kn)和γ_S(■∨W_(1·n)).     

Hiong不等式的推广

本文研究了Фff^（k）的值分布，这里的f为超越整函数。Ф是满足T（r，Ф）=S（r，f）的亚纯函数．k为正整数，得到的结果推广了Hiong和Yu的结果。并回答了Yu提出的问题。     

顶点Folkman数的上界

证明关于顶点Folkman数上界的新不等式.特别地,用构造性方法证明:对于任意满足00和c(r)>0使得Fv(k,k;k 1)≤c(r)(k-1)1/4log2(k-1)-r对任意的k≥N(r)成立,其中N(r)和c(r)都是只依赖于r的常数.     

一类固定系数解析函数的极值点与支撑点

摘要 设Q={f(z):f(z)=z-an+1zn+1-(∞∑k=n+2)akzk},这里an+1=c(n+2)/(n+1)(n+3),ak≥0,∞∑k=n+2k(k+2)/k+1ak≤1-c,0≤c≤1,n∈N,并且f(z)在单位圆盘△={z:| z |＜1}内解析,得到函数族Q的极值点与支撑点.     

图的L(d,1,1)-标号

给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λ_d,1,1(G)≤Δ³-Δ²+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λ_d,1,1(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图： 拟正则树T_Δ及正则毛毛虫Cat_n, 给出了确切的L(d,1,1)-标号数, 其中d≥2.     

涉及分担值的一个正规定则

主要得到了以下结果:设是一族平面区域D内的亚纯函数,a,b为有穷非零复数,k为大于1的整数.如果对于F中的任一元素f,满足f-a的零点重数至少为k,f(z)=a■f(k)(z)=a,f(k)(z)=b■f(k+1)(z)=b,则当k≥3时,F为正规族,k=2并且a/b≠4时,F为正规族.并且给出了1个例子说明条件a/b≠4是必要的.     

关于Hayman猜想的正规定则的推广

在一般条件f(k)(z)-afk+1(z)≠b下研究正规性,推广了以往在条件f(′z)-afn(z)≠b下研究正规性问题,从而改进了以往结论,即设F是区域D上的亚纯函数族,a≠0和b是两个有穷复数,k为一正整数,如果F内的每个函数f(z)都满足f(k)(z)-afk+1(z)≠b,并且f(z)的极点重数≥k+1,零点重数≥2,则F在D内是正规的.     

涉及单向分担集的亚纯函数族的正规性

证明了定义在单位圆盘上的亚纯函数族F满足对于任意f∈F(f的零点重数至少k级),并且存在c>0使得如果f(z)=0有|f(k)(z)|c且-Ef(k)(S)-Ef(S)(S={a,b}),那么F在单位圆盘上正规.     

上三角矩阵环的半交换子环

研究了约化环R上的n阶上三角矩阵子环An（R）（n=2k＋1≥3）,An（R）＋RE1,k（n=2k≥4）的半交换性,在此基础上，给出了一些上三角矩阵环的极大半交换子环．     

关于微分单项式的值分布

设M[f]=f~(n_o)(f′)~(n_o)…(f~(K))~(nK)是亚纯函数f的微分单项式,次数和权分别为d和W。本文证明,当n_o=1时,若W<3d-(8/3),那么当N_1)(r,1/f)=S(r,f)时,M[f]-1有无穷多个零点。它是L.R.Sons一个结果的补充。利用本文结果可以部分地解决Hayman问题1.19。     

有限域上(n,k)(k\geq 3)型高斯正规基的对偶基的复杂度

熟知, 有限域上的正规基在计算机的软件和硬件实现中都有广泛的作用, 尤其令人感兴趣的是确定有限域上的正规基, 特别是高斯正规基的复杂度. 通过利用有限域的性质与初等的技巧, 给出了有限域上一类(n,k)(k\geq 3)型高斯正规基的对偶基的复杂度的上下界, 由此确定了有限域上(n,k)(k=1,2)高斯正规基的对偶基的准确复杂度, 从而简化了万哲先等人在2007年给出的证明.     

齐型空间上Lipschitz函数的一个新刻画

~~的核 Sk( x,y)附加了对称性的要求 .本研究在文 [3]的基础上 ,利用最近 Y.S.Han在文 [2 ]给出的恒等逼近的改进定义给出了 Lipschitz函数类 Lipα的一个新刻画 ,是文 [3]结果的推广 ,其主要结果如下 .定理　设算子列 {Sk}k∈ z[2 ]是齐型空间 ( X,ρ,μ)上的恒等逼近 ,Dk=Sk- Sk-1,f是在任有界集上可积的函数 ,0 <α 相似文献