检索结果-内蒙古大学图书馆

软件学报 2006年第5期17卷 1204-1212页

作者：许道云贵州大学计算机科学系贵州贵阳550025

合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式... 详细信息

合取范式(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中不可满足公式构造的原理和方法.

关键词：极小不可满足公式问题多项式归约 NP-完全公式构造

来源：评论

学校读者我要写书评

暂无评论

极小不可满足公式的某些子类

极小不可满足公式的某些子类

引用

作者：徐小萍南京大学

学位级别：硕士

一个合取范式(CNF)命题公式F称为极小不可满足公式，如果F不可满足，但从F中删去任何一个子句后得到一可满足公式。极小不可满足公式类记为MU，MU的判定问题是Dp-完全的，其中Dp是两个NP-问题之差的问题类。对于CNF公式F，我们记d(F)为... 详细信息

一个合取范式(CNF)命题公式F称为极小不可满足公式，如果F不可满足，但从F中删去任何一个子句后得到一可满足公式。极小不可满足公式类记为MU，MU的判定问题是Dp-完全的，其中Dp是两个NP-问题之差的问题类。对于CNF公式F，我们记d(F)为F的子句数和变元数之差，MU(k)表示差为k的极小不可满足公式所构成的集合。对于固定的k，差为k的公式的满足性问题仍是NP-完全的。但可断言：差为k的公式的极小不可满足性问题可在多项式时间内被解决。\n 在第三章中，我们主要研究了HIT-MU(2)，Unique-MU(2)，MAX(2)，MARG(2)和SYM-MU(2)的结构和复杂度，但MARG(2)的复杂度还未被解决。在结构方面，结果如下：HIT-MU(2)中的公式要么是在经过适当的改名和调整变元顺序后为F22或F22，要么是某一文字在其中仅出现一次的公式；MAX(2)中的公式要么是经过适当的改名和调整变元顺序后为F22，要么是某一文字在其中仅出现一次的公式；MARG(2)中的公式由F22和某一文字在其中仅出现一次的公式组成；Unique-MU(2)和SYM-MU(2)则仅含有一个公式F22。至于复杂度方面：HIT-MU(2)和MAX(2)可在时间O(n3)内被解决，Unique-MU(2)和SYM-MU(2)则可在线性时间内被解决。\n 在第四章中我们研究了HIT-MU，Unique-MU，MAX，MARG，SYM-MU，Dis-MU和CCNF之间的包含关系。其结果是：CCNF包含于HIT-MU，Unique-MU，MAX，MARG，SYM-MU和Dis-MU，HIT-MU包含于MAX，Dis-MU包含于Unique-MU，其它的包含关系都不成立。

关键词：极小不可满足公式合取范式调整变元顺序

来源：评论

学校读者我要写书评

暂无评论

极小不可满足公式在CNF公式类归约中的应用

极小不可满足公式在CNF公式类归约中的应用

引用

作者：王健贵州大学

学位级别：硕士

经典逻辑中的SAT问题是指布尔表达式的可满足性问题，它是计算机科学中的核心问题。SAT问题是NP完全问题，从理论上说，SAT问题不能在多项式时间内解决，它超出了现代计算机的能力。所以，SAT问题是计算机科学发展中的“瓶颈”问题，计... 详细信息

经典逻辑中的SAT问题是指布尔表达式的可满足性问题，它是计算机科学中的核心问题。SAT问题是NP完全问题，从理论上说，SAT问题不能在多项式时间内解决，它超出了现代计算机的能力。所以，SAT问题是计算机科学发展中的“瓶颈”问题，计算机科学家们一直都在寻求各种快速策略和方法试图改进SAT问题的求解。\n　　一个CNF公式是有限个子句的合取，k-CNF是子句长度不超过k的公式类，k-SAT就是判定给定的k-CNF公式是否有可满足的解。众所周知，2-SAT问题是线性时间可解的，而k-SAT问题是NP完全的。近年来，寻找k-SAT的最优算法一直没有停止过。最新研究结果表明改进的关于k-SAT的指数时间算法的复杂度随k的递增而增加。在文献[IP99]中，***和R.

关键词：数理逻辑极小不可满足公式公式归约

来源：评论

学校读者我要写书评

暂无评论

关键文字和极小不可满足公式

关键文字和极小不可满足公式

引用

作者：张秋菊贵州大学

学位级别：硕士

命题变元及其否定统称为文字，文字的析取称为子句，子句的合取称为合取范式（CNF公式）。如果存在一个赋值使得公式的值为1，则称该公式可满足；否则称该公式不可满足。判定一个公式是否是可满足的问题称为可满足性问题，简称为SAT问... 详细信息

命题变元及其否定统称为文字，文字的析取称为子句，子句的合取称为合取范式（CNF公式）。如果存在一个赋值使得公式的值为1，则称该公式可满足；否则称该公式不可满足。判定一个公式是否是可满足的问题称为可满足性问题，简称为SAT问题。解决SAT问题的一个重要算法是DPLL算法。一个公式是极小不可满足的是指该公式本身不可满足，但是从中删去任意一个子句后得到的公式可满足。德国学者H．K．Büning，***等人在这方面做了许多重要的工作。极小不可满足公式的结构和性质将有助于判定SAT算法的研究。对于3-SAT来说，很多学者所做的大量实验表明，在m/n大约为4．26时（其中m是子句个数，n是变元个数），可满足概率为0．5。一般认为，在这个比值下随机生成的3-SAT问题实例非常难解决，而在其它比值下生成的实例容易解决，这种容易-困难-容易的现象就是所谓的相变现象，它原本是物理学中的概念。基于相变现象，Monasson等人于1999年介绍了最大可满足公式的脊。在最大可满足赋值中均取真的文字构成的集合称为最大可满足公式的脊。Dubois等人于2001年根据可满足公式脊的概念，定义了寻找可满足公式的脊的启发式算法，但是没有进行理论研究。本文在启发式算法的基础上，一方面定义可满足公式的关键文字，研究关键文字的性质，给出DPLL算法的一种改进方法；另一方面，利用极小不可满足公式的特殊结构，定义极小不可满足公式的相对关键文字，研究相对关键文字与极小不可满足公式之间的关系，可以证明，仅使用关键文字规则和纯文字规则，就可以将MU（1）公式的任何最大可满足子公式在O（n2）时间内化简为空集。

关键词：关键文字脊可满足公式极小不可满足公式算法复杂性

来源：评论

学校读者我要写书评

暂无评论

可满足公式到极小不可满足公式MU(1)的扩张复杂性(英文)

引用

贵州大学学报（自然科学版） 2005年第4期22卷 348-358页

作者：张庆顺许道云贵州大学计算机科学系贵州贵阳550025

可满足合取范式(CNF)公式F到极小不可满足公式MU(1)的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var(G)var(F)并使得F+G∈MU(1)。Horn公式到MU(1)公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解... 详细信息

可满足合取范式(CNF)公式F到极小不可满足公式MU(1)的扩张是,对给定的CNF公式F,是否存在一个公式G满足条件var(G)var(F)并使得F+G∈MU(1)。Horn公式到MU(1)公式的扩张问题可在多项式时间内解决,但对一般CNF公式F的扩张问题,至今尚未解决。这里我们将给出一个多项式时间的算法解决这一问题。

关键词：变量出现极小不可满足公式公式的扩张

来源：评论

学校读者我要写书评

暂无评论

一个极小不可满足公式子类的等价结构(英文)

引用

贵州大学学报（自然科学版） 2001年第2期18卷 79-89,102页

作者：许道云贵州大学计算机科学系贵阳550025

研究一个极小不可满足公式子类 (MAX( 1 ) )的等价结构考虑了MAX( 1 )上的变元改名问题和文字改名问题此两个问题均可在O(nlog2 (n) )

关键词：极小不可满足公式变元改名等价结构文字改名 MAX(1) O时间

来源：评论

学校读者我要写书评

暂无评论

一个极小不可满足公式子集的构造

引用

洛阳理工学院学报（自然科学版） 2011年第4期21卷 77-79,87页

作者：陈庆燕姚雷博滨州学院计算机系山东滨州256600 洛阳理工学院电气工程与自动化系河南洛阳471023

对于极小不可满足公式和它的子类的研究是近年来兴起的一个热门方向。极小不可满足公式通过分裂得到的公式保持了极小不可满足性,它的子类的某些性质对于建立在分裂上的归纳证明是很有用的。找到了一个能递归构造的极小不可满足公式的子... 详细信息

对于极小不可满足公式和它的子类的研究是近年来兴起的一个热门方向。极小不可满足公式通过分裂得到的公式保持了极小不可满足性,它的子类的某些性质对于建立在分裂上的归纳证明是很有用的。找到了一个能递归构造的极小不可满足公式的子类MAX+,并证明这种递归构造方法具有可靠性和完备性,最后给出了一个构造实例。

关键词：极小不可满足公式 MAX+(k)公式集分裂对

来源：评论

学校读者我要写书评

暂无评论

一个极小不可满足公式子类改名的复杂性研究

引用

滨州学院学报 2011年第6期27卷 82-85页

作者：陈庆燕滨州学院计算机科学技术系山东滨州256603

改名规则在创建有效的满足性算法和简化某些消解难例的证明中起到了重要作用,对于一些具有对称结构的难例公式,可以通过改名来降低其证明的复杂性.研究了一个极小不可满足公式子类,给出了该子类的改名算法,并证明了对该子类中改名问题... 详细信息

改名规则在创建有效的满足性算法和简化某些消解难例的证明中起到了重要作用,对于一些具有对称结构的难例公式,可以通过改名来降低其证明的复杂性.研究了一个极小不可满足公式子类,给出了该子类的改名算法,并证明了对该子类中改名问题可以在多项式时间内判定.

关键词：改名极小不可满足公式子类多项式时间

来源：评论

学校读者我要写书评

暂无评论

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

引用

软件学报 2006年第7期17卷 1517-1526页

作者：许道云董改芳王健贵州大学计算机科学系贵州贵阳550025 内蒙古农业大学计算机与信息工程学院内蒙古呼和浩特010018 软件工程国家重点实验室(武汉大学) 湖北武汉430072

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题“对于给定的CNF公式H和F是否存在一个变元(或文字)改... 详细信息

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

关键词：计算复杂性改名极小不可满足公式

来源：评论

学校读者我要写书评

暂无评论

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

引用

软件学报 2008年第3期19卷 511-521页

作者：许道云邓天炎张庆顺贵州大学计算机科学系贵州贵阳550025

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,... 详细信息

合取范式(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是否含有不可满足公式.***等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.

关键词：线性CNF公式不可满足性 NP-完全性极小不可满足公式归约

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：