k-LSAT(k≥3)是NP-完全的(英文)

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.     

极小不可满足公式在多项式归约中的应用

合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(＞3)的子句,仅需引入|l/2|个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.     

不可满足公式的同态证明系统

合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.     

MAX(1)和MARG(1)中公式改名的复杂性

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.     

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

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

一个正则NP-完全问题及其不可近似性

通过一个适当的归约变换,可以将一个CNF (conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性.带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性.极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足.借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换.这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4.因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

取定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取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

结合可信度的km-means算法

以K-means为代表的聚类算法被广泛地应用在许多领域, 但是K-means不能直接处理不完整数据集. k_m-means是一种处理不完整数据集的聚类算法, 通过调整局部距离计算方式, 减少不完整数据对聚类过程的影响. 然而k_m-means初始化阶段选取的聚类中心存在较大的不可靠性, 容易陷入局部最优解. 针对此问题, 本文引入可信度, 提出了结合可信度的k_m-means聚类算法, 通过可信度调整距离计算, 增大初始化过程中选取聚类中心的可靠性, 提高聚类算法的准确度. 最后, 通过UCI和UCR数据集验证算法的有效性.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

Filtering of some nonlinear diffusions satisfying the general Bene condition

Under some regularity assumptions and the following generalization of the well-known Bene condition [1]:

Full-size image

, where F(t,z) = g⁻²(t)∫f(t,z)dz, F_t, F_z, F_zz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density q_t(z, x) α Px_t ε dz| y_s, 0 st, where diffusion x_t on R¹ solves x₀ = x, dx_t = [β(t) + α(t)x_t + f(t, x_t] dt + g(t) dw₁, and observation y_t = ∫_o^th(s)x_s ds + ∫_o^t(s) dw_2t, with w = (w₁, w₂) a two-dimensional Wiener process.     

LaTeX数学表达式解析与索引方法

针对数学表达式复杂二维结构特性所导致的普通文本检索技术难以对其进行检索的问题,提出了一种面向数学检索的LaTeX数学表达式解析与索引方法。在充分考虑公式特点的基础上,通过对LaTeX构成特点的分析和归纳,设计了LaTeX数学表达式的解析和检索特征提取算法;以此为基础,构建了一种适应数学表达式特性的双层索引结构,利用所提取数学表达式各层次运算数和运算符信息,分别以Treap数据结构和倒排索引结构构成数学表达式索引,为实现进一步的数学表达式检索匹配打下基础。在浏览器/服务器模式下采用6234条数学教材中的公式作为数据集进行实验,在解析获得的124960个基线层数最高为11层的表达式节点上,建立索引平均耗时为33.8317 s。实验结果表明所提出的LaTeX表达式解析算法和索引结构能够适应数学表达式的特点,有助于实现具有较高效率和准确性的数学表达式检索。     

基于模糊分类的印刷体数学公式抽取方法

公式抽取是印刷体数学公式识别的基础性环节，现有的识别方法多以公式区域已知为前提，相关的研究还很欠缺。通过引入模糊分类理论，提出了一种孤立数学公式的抽取算法，通过对大量训练样张的数据统计与分析，选取了非规则度、宽高比、密度等6维特征，由此构建出对孤立公式行、文本行、标题行的模糊分类规则，实现了孤立公式行的抽取。实验结果表明，该方法有较高的准确性和鲁棒性。     

New predictor corrector trapezoidal formulae for solving initial value problems

In Evans and Sanugi [3] a new class of nonlinear methods based on Euler's integration formula for solving ordinary differential equations was presented. In this paper, consideration is given to the development of predictor-corrector based methods using this new strategy for solving initial value problems.     

数学公式基线结构分析及识别算法研究

公式识别问题被分为字符分割和结构分析两部分内容。系统地研究了数学公式识别的全过程,使用自适应字符分割方法和基线结构分析算法成功地实现了一般数学公式的识别,识别率比较高,较好地完成了公式识别任务。从实验结果中可以看出,这种基于基线结构分析的数学公式识别方法能够满足大多数印刷体公式的识别,是一种较好的方法。     

A Refinement of the Black-Scholes Formula of Pricing Options

A central problem of actuarial mathematics, i.e., the problem of pricing options (documents of a certain form that grant rights to buy or sell securities in the future), is considered. The well-known Black-Scholes approximate formula for pricing options is refined.     

一种新型逻辑函数化简方法——立体化简法

文章在卡诺图化简法的思想基础上设计了一种新型的逻辑函数化简方法——“立体化简法”。用逻辑函数立方体代替卡诺图来表示逻辑函数,在三维立体空间进行逻辑函数的化简,既保持了卡诺图化简法方便、直观、容易掌握的优点,又使得可以方便化简的逻辑函数变量增加至六个;如果采用达到卡诺图化简法五、六变量逻辑函数化简的难易程度的方法,可使化简的逻辑函数变量增加至九个。这种新型的逻辑化简方法使得五、六变量逻辑函数的化简变得非常简单、方便,也使得九变量以内的逻辑函数的化简变得直观、可行。     

MIS中自定义计算公式方法的研究与应用

讨论了在各类管理信息系统的开发过程中,由系统最终用户根据自身的具体需求自行定义系统中某些项目的计算公式的重要性和必要性.在介绍了目前常见的几种自定义计算项目和自定义计算公式的方法并分析其利弊之后,对其中一类典型的方法进行了深入分析.详细地说明了系统的结构模型,计算项目的属性定义,自定义计算公式的解析方法及计算过程.最后,以一个具体的应用实例对其使用方法和设计技巧作了说明.     

用有向图法解决公式循环依赖问题

用户使用报表系统时，在自定义的公式集合中可能存在公式循环依赖问题，用一种有效的方法发现这一隐藏错误是设计报表系统的一项关键技术。研究了用有向图法解决报表系统中的公式循环依赖问题，提出了报表系统中的公式循环依赖问题；引用有向图和集合论上的关系等概念对公式循环依赖进行了形式定义，证明了公式循环依赖的判定方法；给出了公式依赖关系图的构造算法和用有向图法解决公式循环依赖的算法。