逼近4正则图的最小顶点覆盖问题的难解性(英文)

证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.     

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）内被判定。     

一类新型Kantorovich算子在Orlicz空间内的逼近逆定理

利用加权光滑模和K-泛涵,研究一类新的Kantorovich型算子在Orlicz空间内的逼近逆问题,得到了弱型逼近逆定理.     

模归约算法的数学基础研究

 多项式模归约算法是计算机代数中的基本问题之一,在编码算法和密码体制设计中有着广泛应用.提出了模归约算法中的2类基本算子:字归约算子、半字归约算子,并进一步证明了2类算子的计算量具有某种形式的不变量(如果满足一定的条件),从而证明了模归约算法计算量的线性性质,为其算法设计和分析提供了理论基础.还通过实例给出了2个算子在ECC和AES密码算法中的一些应用.     

模糊系统中方形分片线性函数依K-积分模的泛逼近性

首先引入方形分片线性函数和K-拟可加积分的概念,应用诱导算子及积分转换定理证明了方形分片线性函数在K-积分模意义下对一类可积函数的泛逼近性.该结果表明:模糊系统中方形分片线性函数对连续函数的逼近能力可以推广为对一般可积系统的逼近能力.     

A-调和逼近技巧与非线性椭圆方程组的部分正则性

应用一个新方法,即用A 调和逼近技巧考虑了具有可控增长条件的非线性椭圆方程组弱解的部分正则性.改进了以往部分正则性的结果,直接建立了弱解的导数在正则集上的最优H lder指标,结果的证明主要是将A 调和逼近引理与第2Caccioppoli不等式巧妙结合起来.首先,证明g=u-p0(x-x0)γ(γ是某常数)满足A 调和逼近引理中g的性质,于是找到一个具有许多好性质的A 调和函数h.从而对g的梯度的L2模估计通过第2Caccioppoli不等式变为对g本身的L2估计,再应用A 调和逼近引理转化对A 调和函数h的估计,进而得到了正则性所要的标准估计式.     

一类积分型算子在Orlicz空间内的逼近性质

以Baskakov算子和Beta算子为基础,构造了一类积分型算子,研究该算子在Orlicz空间内的逼近问题。利用Hardy-Littlewood极大函数、N函数的凸性、Jensen不等式以及K-泛函与连续模等工具,给出该算子在Orlicz空间内逼近的正、逆定理及等价定理。     

随机图的哈密尔顿回路实验研究

哈密尔顿回路问题是图论的经典NP-难解问题之一,在计算机科学中被广泛用作测试用例以测试算法/系统的有效性,包括可满足性(SAT)、回答集程序设计(ASP)以及约束可满足问题(CSP)等.在本文中,我们通过ASP实验研究了40到100个节点(步长为10)随机图的哈密尔顿回路存在性、不存在性、以及难于计算等的分布情况,结果表明它们都具有一定的规律.这不仅对随机图的哈密尔顿回路本身是有益的探索,也为生成随机图哈密尔顿测试用例提供了有益的指导.     

含盐条件下偶氮染料兼厌氧性生物的降解性能

研究活性染料与不同浓度葡萄糖共基质条件下的兼厌氧性生物降解性能和K-2BP在不同盐浓度条件下的兼厌氧性生物降解性能.选择K-2BP作为目标污染物进行静态反应器生物降解实验.结果表明,兼厌氧性微生物在只有K-2BP作为基质时对染料的降解率较低,葡萄糖存在时,能提高兼厌氧性生物对染料的降解能力;葡萄糖为800mg/L时6h染料降解率为64.1%,而葡萄糖浓度为1 000mg/L时,不利于染料降解,6h染料降解率为46%,与不投加葡萄糖情况的降解率接近.葡萄糖浓度为800mg/L,盐浓度分别为2g/L,5g/L,10g/L和20g/L,其一级降解动力常数分别为0.105 78mg/L.h,0.049 47mg/L.h,0.028 69mg/L.h,0.022 75mg/L.h;半衰期分别为6.99h,14.15h,22.55h,30.21h.随盐浓度梯度升高,染料的兼厌氧性降解动力学常数逐渐降低,高盐浓度会抑制兼厌氧性微生物对染料的降解.     

最大节约原则下单体型推导问题的复杂性

基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题,证明了该问题是NP-hard以及MAX-SNP完全的,从而解决了该问题在计算上的复杂性.这一结果显示,除非P等于NP,否则,该问题不存在多项式时间算法;甚至存在一个常数e> 0,该问题不存在比1 e好的近似算法.     

Retrieval and analysis of sea surface air temperature and relative humidity

Air temperature and relative humidity have been the main parameters of meteorology study.In the past data could be obtained from in-situ observations,but the observations are local and sparse,especially over ocean.Now we can get them from satellites,yet it is hard to estimate them from satellites directly so far.This paper presents a new method to retrieve monthly averaged sea air temperature(SAT) and relative humidity(RH) near sea surface from satellite data with artificial neural networks(ANN).Compared with the observations in Pacific and Atlantic,the root mean square(RMS) and the correlation between the estimated SAT and the observations are about 0.911 and0.99,respectively.The RMS and the correlation of RH are about 3.73%and 0.65,respectively.Compared with the multiple regression mediod,the ANN methodology is more powerful in building nonlinear relations in this research.Thus the global monthly average SAT and RH are retrieved from the fixed ANN network from July 1987 to May 2004.In general the annual average SAT shows the increasing trend in recent 18 years.The abnormality of SAT is decomposed with the empirical orthogonal function(EOF).The leading three EOFs could explain 84%of the total variation.EOF1(76.1%) presents the seasonal change of the SAT abnormality.EOF2(4.6%) is mainly related with ENSO.EOF3(3.3%) shows some new interesting phenomena appearing in the three main currents in Pacific,Atlantic and Indian Ocean.     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

氨基酸分类与蛋白质二级结构相关性

从氨基酸序列和蛋白质二级结构相关性出发 ,定义信息剩余度 ,通过信息剩余度极大化 ,推导出从 2 0组到 2组的氨基酸分类结果 ,同时也得到了信息剩余度极大值 (RMAX)与约化次数的关系     

Some variants of SAT and their properties

A new model for the well-known problem, the satisfiablility problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their properties are presented. Denote by NP the class of all languages which can be decided by a non-deterministic polynomial Turing machine and by P the class of all languages which can be decided by a deterministic polynomial-time Turing machine. This model also allows us to give another candidate for the natural problems in ((NP-NPC)-P), denoted as NPI, under the assumption P≠NP, where NPC represents NP-complete. It is proven that this candidate is not in NPC under P≠NP. While, it is indeed in NPI under some stronger but reasonable assumption, specifically, under the Exponential-Time Hypothesis (ETH). Thus we can partially solve this long standing important open problem.     

基于学习的GSAT算法

在GSAT算法的基础上，引进学习的概念，设计了一种新的SAT求解算法，用若干DIMAC的测试实例进行了仿真实验研究，比较了基于学习的GSAT算法与著名的Random Walk GSAT算法，结果表明两种算法对于随机SAT的实例比较有效，但对于Real-World SAT的实例性能较差。     

Quasi-Regression基函数的选择和算法改进

Quasi—Regression主要用于解决高维空间的函数逼近问题．函数的拟合效果依赖于所选择的标准正交基函数和拟合算法．在很多情况下，未知函数可以表示成若干个部分变量的函数和．本对此提出了一种函数的拟合算法，通过对这些部分变量的函数的拟合，得到原函数的拟合，并且说明新方法精度更高，计算量更少．     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

张量积等距曲面的样条逼近

在几何造型系统中,通常需要用低次有理参数曲线、曲面来逼近等距曲线、曲面.这篇文章主要研究张量积等距曲面的样条逼近.利用样条曲面和原曲面加权组合构造一个新的有理曲面,该曲面通过插值原曲面的等距曲面上的采样点,从而逼近等距曲面.此方法较为简单,逼近曲面的次数不会超过原曲面,逼近曲面能达到C2连续.由插值点决定控制点的个数和逼近所能达到的误差精度,而且可以通过调节权值使等距曲面达到最佳逼近.     

一种求解难SAT问题的改进DP算法

DP算法是求解SAT问题的最有效完全算法之一，论文分析和讨论了DP算法中的各种分枝文字策略，并基于对不满足解数估计的方法，提出了一个有效的分枝文字策略，实验结果表明，提出的改进DP算法对难SAT实例有较好的平均性能。