随机正则3-可满足性问题的解簇结构分析

正则3-可满足性(3-SAT)问题是一个NP难问题,研究正则3-SAT问题解簇结构变化,旨在深入理解该问题的判定难度和可满足性解的分布情况。然而,现有分析模型只研究了接近簇集相变点的几个离散值,在不同约束密度下,缺乏统一的分析模型来描述解簇的结构演变。为了解决这一问题,提出解簇结构相变分析模型(PMSS)。该模型主要思想是采用WalkSAT算法和信息传播算法求得正则3-SAT问题可满足的初始解,再利用随机游走构造该初始解的解簇,并对解簇进行分析。用模块度和社区度量解簇社区结构,用结构熵度量解簇结构复杂性。实验结果表明,PMSS能够准确分析解簇结构演变过程,并且正则3-SAT问题实例的可满足相变点位于13~14,与使用Zchaff求解器得到的相变点一致,进一步验证了PMSS的有效性。

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则(k,2s)-CNF公式.受严格正则(k,2s)-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则(k,2s)-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机(k,2s)-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机(3,2s)-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机(3,2s)-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机(3,2s)-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.

一类A-调和方程的障碍问题的很弱解的全局正则性

应用Hodge分解定理,得到了非齐次A-调和方程-div(A(x,Du(x)))=f(x,u(x))对应的障碍问题很弱解的局部和全局的W^(1,q)(Ω)-正则性,其中,A(x,Du(x)),f(x,u(x))满足文中所给的条件,从而推广了相关文献中的有关结果.该结果在优化控制问题中有着广泛的应用.

A-调和方程障碍问题解的局部正则性

给出拟线性散度型椭圆方程divA(x,u(x))=0的Kψ,θ-障碍问题解的局部正则性结果,其中A(x,ξ)满足强制性与控制增长条件,自然指数p∈(1,n),障碍函数ψ≥0.

基于因子图求解(3,4=)-CNF公式类下可满足问题

合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次。与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图。对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7-路径因子,则F可满足。

基于图分解的(3,4)-CNF公式的可满足性

对于规则的(3,4)-CNF公式F,公式F对应的因子图GF恰好是一个(3,4)-双向正则二部图。利用正则二部图的有关性质,证明了对于任意的(3,4)-CNF公式F,若其对应的因子图GF能够被划分为两个(3,2)-双向正则二部图,则F是可满足的。

3维不可压Boussinesq方程在BMO^(-1)空间和各向异性Lorentz空间中的正则性准则

主要研究3维不可压Boussinesq方程解的正则性问题,运用能量估计的方法,证明了在BMO^(-1)空间意义下涡度▽×u的正则性准则.另外,用同样的方法,还证得在各向异性Lorentz空间下关于压力π的一个正则性准则.所得结果推广了已有的结论.

微分形式障碍问题解的正则性

首先给出微分形式障碍问题解的定义,然后利用微分形式技巧得到了一个弱逆Hlder不等式,并得用Gehring引理的推广形式得到解的高阶可积性.

一类双障碍问题的很弱解的全局正则性

应用Hodge分解定理,得到了非齐次A-调和方程-divA(x,Du(x))=f(x,u(x))对应控制的双障碍问题的很弱解W1,q(Ω)-正则性,其中,A(x,Du(x)),f(x,u(x))满足文中所给的条件,从而推广了相关文献中的有关结果.该结果在优化控制问题中有着广泛的应用.

光滑互补函数与互补问题的2-正则解

研究了用光滑互补函数将互补问题转化为非线性方程组时产生的正则性问题。光滑互补函数通常会导致再生方程组产生奇异解,而2-正则性条件是解决奇异性问题的一种工具。在分析了光滑互补函数与二次正齐次函数性质的基础上,给出了2-正则性的成立条件。证明了在很弱的条件下,利用二次正齐次的光滑互补函数可使再生方程组的2-正则性严格地弱于原问题的b-正则性,并说明了已有文献采用的互补函数是此类函数的一个特例,还给出了一类新的符合条件的互补函数。

改进的模拟退火算法求解规则可满足性问题

对于随机k-SAT问题,限定每个变元出现的次数恰好出现d次,形成随机规则(k,d)-SAT问题,目前国内外对该问题的相关研究较少,且研究随机规则(k,d)-SAT问题比研究k-SAT问题更为具体。文中给出一种随机规则(k,d)-SAT问题的生成实例模型——RRIG(N,k,d)模型,并用改进的模拟退火算法SARSAT求解规则随机规则(k,d)-SAT问题。将变元出现次数d加入到扰动策略中,利用变元出现次数和子句间约束关系中的启发信息对候选解中的赋值选择性改动,加快算法收敛至较优解的速度;同时,模拟退火算法中的Metropolis接受准则和改进后的退火策略保证了算法能够有效跳出局部最优解,最后使用RRIG(N,k,d)模型生成不同参数的测试实例,并与其他相关算法进行比较,结果表明SARSAT算法能有效解决规则可满足问题。

3—连通、3—正则图中的圈

本文介绍了3—连通、3—正则图中包含给定点集的大子集的圈。

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

为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当s<s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率可满足;当s>s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率不可满足.最后,选取了k=4和k=6的两组数据集进行实验验证,结果表明理论结果与实验结果符合.

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.

大数据查询路径和类型决策问题的研究

用正则树表示的XML数据中对XPath的决策问题,是大数据查询中常见的方法之一,本文提出了一套实用的、有效的数学模型来解决XPath表达式中的可满足性问题。并通过对一些决策问题,例如带或者不带类型约束的XPath的空、包含、重叠和覆盖问题的实验对于算法进行了证实,实验证明该系统能够有效的被使用于对操作XPath表达式和XML类型注释的程序语言的静态分析器中。

一类可分离SAT问题的O(1.890~n)精确算法

布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)~n),当k=3时,最好算法时间复杂度为O(1.308~n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890~n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890~n)精确算法,该算法与子句长度无关.

一种布尔公式的代数逻辑约化新方法

布尔可满足问题是最早被证明的NP完全问题之一,1-in-3-SAT问题是一个NP完全的布尔可满足子类问题。1-in-3-SAT的计算复杂度取决于对应公式的变量以及子句的个数。将1-in-3公式归约为一个变量数或者子句数更少的1-in-3公式,是提高1-in-3-SAT问题求解效率的一个关键。基于一个新的范式形式——XCNF,针对1-in-3-SAT问题提出一种新的代数逻辑约化方法,用于在多项式时间内约减一个1-in-3公式的变量数和子句数。所提算法的主要思想为:首先将1-in-3公式转化为XCNF公式,然后尝试找出XCNF公式中的X-纯文字,并利用X-纯文字法则对1-in-3公式中相应的布尔变量赋值,最后得到一个约减公式,该约减公式与原公式的1-in-3可满足性等价。

解非线性互补问题的光滑牛顿方法

由于退化解会导致再生方程的奇异性,非线性互补问题的求解通常采用基于半光滑技术的广义牛顿法.基于2-正则性的概念,提出了一类利用光滑互补函数求解互补问题的光滑牛顿算法.算法采用积极集技术,能在解的附近估计出退化指标,并把原问题降阶为一个非奇异方程组,从而保证了迭代效率.算法具有整体收敛性和局部超线性收敛性,数值实验显示算法是有效的.

植物抗病激活剂诱导植物抗病性的研究进展

植物抗病激活剂本身及其代谢物无直接的杀菌活性,但可刺激植物的免疫系统而诱导植物产生具有广谱性、持久性和滞后性的系统获得性抗病性能(SAR)。植物抗病激活剂的诱导除了可以引起植物富含羟脯氨酸糖蛋白(HRGP)的变化,导致木质素在细胞壁沉积,使植物形成物理防御机制外,经植物抗病激活剂诱导后的植株能导致内源水杨酸(SA)的累积、形成氧化激增,植物局部细胞程序化死亡而产生过敏反应(HR),植物抗病激活剂诱导后产生的抗病信号经内源信号传导物质 SA、茉莉酸(JA)、乙烯(Et)和一氧化氮(NO)可传导到达整个植株,经过一系列抗病相关基因的调控和表达可引起寄主防御酶系如苯丙氨酸解氨酶(PAL)、β-1,3-葡聚糖酶(β-1,3-glucanase)、几丁质酶(chitinase)、过氧化物酶(POX)等以及抗病物质如木质素与植保素等的变化及病程相关蛋白(PRP)的调控与表达。文中讨论了植物抗病激活剂概念和种类及其诱导抗病作用的主导机制,指出了植物抗病激活剂的应用前景和发展方向及使用和研究开发中可能存在的问题与对策。

GLOBAL COUPLING OF AN INTEREFACE PROBLEM IN AN ACTIVATIOR—INHIBITOR SYSTEM

An activatior-inhibitor reaction system with global coupling was intro-duced in [1],The authors showed that global coupling suppresses the breathing motion and enhances the propagation of the localized solution.The collision between two trav-eling waves for a sufficiently strong global coupling is discussed in [2].If the width of layers is infinitesimally thin,the equation of motion for a pair of the interfaces is derived.We shall study the dynamics of interfaces in the free boundary problem with global coupling and with a strong global coupling.