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-完全的.

子句型缺省逻辑中的分情形推理(英文)

引进一种树型方法以研究缺省逻辑中分情形推理下的 Roos扩张 ,深入讨论了 Roos扩张的计算 ,并分析了Roos扩张与 Reiter扩张的关系 .为计算 Roos扩张 ,引入了从子句集分解最小文字集的算法 .方法对于在缺省逻辑中计算

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

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

带文字改名策略的DPLL算法

限制在不可满足公式的不可满足性的证明,给出了一个改进的DPLL算法—RSMLS。新的算法带有一条对称规则(文字改名规则)和三条简化规则((1,*)-消解、子公式、重复规则)。作为一个应用实例,将RSMLS算法应用于鸽巢公式P_(n-1)~n的不可满足性证明。证明了:关于RSMLS算法,公式P_(n-1)~n有一棵反驳证明树至多带有O(n^3)个结点。

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

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

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

合取范式(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)的子句,仅需引入???2l???个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.

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

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

浅析我国中小型物流企业资源的整合

目前,有关物流资源的整合问题已成为物流界较为热门的话题。文章简单介绍我国中小型物流企业的现状,并从企业内部资源、客户资源、物流服务能力资源、信息资源、物流流程五个方面对我国中小型企业的资源整合问题进行探讨。

基于职业岗位能力的高职化工物流管理专业课程体系建设——以南京化工职业技术学院化工物流管理专业为例

高职化工物流管理专业以培养高素质技能型人才的目标为前提,以职业岗位群的能力需求为主线、以人才培养目标为起点、以就业为导向设计学生的课程体系。文章以南京化工职业技术学院化工物流管理专业为例研究高职化工物流管理专业课程体系构建,首先分析高职物流管理专业课程体系现状,然后提出构建基于职业岗位能力的高职化工物流管理专业课程体系,最后对课程体系的实施保障提出了要求。

PCP定理及其在不可近似问题研究中的应用

PCP定理是近十年来计算复杂性领域内的重要成果之一,介绍了从图灵计算模型到概率可验证明(PCP)计算模型的演变过程、PCP系统的基本理论,以及PCP定理应用于不可近似问题研究的基本原理和方法。

浅谈班主任班级管理工作

班级是学院的基本组成单元,班级的好坏直接关系到学院的发展和学生个人的发展。本人认为,有效的班级管理工作应注重班级的学风建设和班风建设。

分析中的可计算性

工程和自然科学中大量的科学计算问题,需要可靠的计算方法和计算软件,通常的实数浮点表示方法只提供了一种逼近实数的基本方法.对实数的不同逼近方法诱导不同的可计算性.对实数的重新理解和认识是研究分析中可计算性的重要基础.Klaus Weihrauch基于第二型图灵计算模型,引入了基于无穷串的可计算函数的概念,并建立了第二型能行计算理论.有关可计算实数理论的几种经典模型可以统一在第二型能行计算理论框架中.对于一般的集合,为研究其中元素的可计算性,引入基于字母集Σ的表示系统.形式上是一个部分函数υ∶Σ*→M或δ∶Σω→M(称为命名系统),不同命名系统下刻画不同的逼近方法,诱导出不同的可计算性,在能行拓扑空间中诱导出不同的拓扑.拓扑与命名系统之间的内在联系,使得抽象空间中可计算性的研究得到自然延伸.

汉语PRECIS的计算机实现

本文叙述了 PRECIS的基本概念和PRECIS的汉语移植。解决了PRECIS应用于汉语中的实际问题。给出了汉语PRECIS的算法,并在PC机上用Turbo C语言实现。该系统具有良好的用户界面,且易于使用。

时间规划的关系矩阵法之简化

就张钹等提出的时间规划的关系矩阵法,提出一个简化方法,这里不再分时间关系的单成分与多成分。简化后的方法对一般情形有效,而且不再考虑相容集,由此算法可以求出所有可能的时间安表排,且计算复杂性仍在多项式时间内。

面向物流职业岗位群的高职人才培养规格研究

针对目前高职物流人才培养规格现状进行相关研究,分析了目前高职人才培养规格存在的问题。结合高职物流企业人才培养规格,选择物流企业进行调研,了解物流职业岗位群及岗位能力要求;了解物流毕业生目前就业现状,通过对比分析和归纳总结,最终根据职业岗位群的要求对物流专业人才培养规格进行准确定位,使培养的学生符合社会、企业需求。

大数据计算的基础理论探究

在经典计算中,对前端输入数据的复杂性不做分析。在大数据计算中,前端输入数据的复杂性分析反而成为大数据计算和分析的重点。本文讨论大数据计算的基础理论问题,将大数据计算问题分为目标任务型和内容认知型。大数据计算形式上依赖于一个外部信息源,从计算的有效性,将大数据计算的讨论限制在对数空间复杂类,涵盖了并行计算复杂类。基于带Oracle的图灵计算模型,限制在对数空间内图灵可计算,并且外部信息源能够用一个对数空间可计算的递归函数枚举,引入了大数据可计算的计算模型和大数据可计算性、可判定问题等概念。

基于物流职业岗位群的高职物流管理专业课程体系构建

高职教育肩负着为经济社会发展培养高素质技能型专门人才的重任。高职物流管理专业课程体系的构建要适应我国物流职业岗位群的能力需求,通过对毕业学生、合作物流企业等多家企业岗位职业能力需求情况进行调查,详细分析目前物流职业岗位群所应具备的知识、能力和素质,在此基础上制定基于物流职业岗位群的高职物流管理专业课程体系,实现专业教学与企业岗位技能需求的零距离对接。

学习《概率论与数理统计》应该注意的若干问题(2)——随机变量与概率分布

阐述随机变量在《概率论与数理统计》中的重要作用,随机变量的引入,可以通过随机变量(作为函数)取值(或取值范围)相同给出事件的一种规范表示,从而数学分析的方法和手段在《概率论与数理统计》中得以充分利用,从随机变量所隐含的不确定性过渡到确定的分析和计算。

4杆汉诺塔的最优移动次数

通常汉诺塔问题只带三根杆,当圆盘数为n时,最优移动次数为T3(n)=2n-1.对于带4杆的汉诺塔问题,最优移动次数满足关系T4(n)=2T4(m)+T3(n-m),其中m=arglmin{2T4(l)+T3(n-l)}依赖于n.对于正数整k,当k(k-1)/2+1≤n≤k(k+1)/2,n=k(k-1)/2+l时,T4(n)=(l+k-2)2k-1+1.特别,T4(sk)=2T4(sk-1)+T3(k),其中s0=0,sk=sk-1+k(k≥1).

浅谈托盘共用系统的建设

主要介绍了托盘在物流系统中的重要作用,托盘共用的概念,根据我国托盘共用的现状和存在的问题,提出建立托盘共用系统的一系列措施。