A polynomial-time algorithm for reducing the number of variables in MAX SAT problem

来源 :中国科学：技术科学英文版 | 被引量 : 0次 | 上传用户：tower2008

【摘要】

：

Maximum satisfiability (MAX SAT) problem is an optimization version of the satisfiability (SAT) problem. This problem arises in certain applications in expert s

【作者】

：

马绍汉梁东敏

【机构】

：

DepartmentofComputerScience,ShandongUniversity,Jinan250100,China,China

【出处】

：

中国科学：技术科学英文版

【发表日期】

：

1997年3期

【关键词】

：

MAX SAT problem BIPARTITE graph INDEPENDENT set complexity. MAX SAT problem bip

【基金项目】

：

Porject supported by the National Natural Science Foundation of China and by the National "863" Hi-Tech Program.

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

Maximum satisfiability (MAX SAT) problem is an optimization version of the satisfiability (SAT) problem. This problem arises in certain applications in expert systems and knowledge base revision. MAX SAT problem is NP-hard Some algorithms can solve this p

其他文献

Effect of thermal convection on colunmar-to-equiaxed transition during solidification of AI-Cualloy

To investigate the effect of three-dimension （3D） thermal convection on columnar-to-equiaxedtransition （CET）, the CET transition during the solidification of an AI-

期刊

columnar-to-equiaxedTRANSITIONAI-CuALLOYSIMULATIONCONVECTIONcolumnar-to-eq

Simulation of casting deformation based on mold surface element method

在团结期间扔过程的变丑思索了许多工程师和科学家多年。以便达到由扔的近网的形成的目标，数字模拟是一个强大的工具。传统的方法计算两个的热压力扔和模子。这个方法承受集中

期刊

塑造表面元素方法扔的热压力模拟扔变丑mold surface element method thermal stress simulation of ca

Pyrolysis characteristics and thermal kinetics of expanded polystyrene(EPS) and styrene-methyl metha

The pyrolysis behaviors of foam patterns have critical influences on fluid morphology and defect formation in Lost Foam Casting (LFC).The pyrolysis behaviors of

期刊

LOSTfoamcastingEPSSt-MMAPYROLYSIScharacteristicsPYROLYSISKINETICS

Experimental studies of superhard materials carbon nitride CNx prepared by ion-beam synthesis method

Formation of superhard materials carbon nitride CNt by using ion-beam synthesis method is reported.100-keV high-dose N+ ions were implanted into carbon thin fil

期刊

ionIMPLANTATIONC≡NCOVALENTbondBURIEDcarbonNITRIDECNXion implantationC≡

Relationship between tensile strength and porosity for high porosity metals

An analysis model has been established according to the structure feature of high porosity metals, and the mathematical relationship between the tensile strengt

期刊

highPOROSITYMETALTENSILESTRENGTHporosity.high porosity metal tensile stren

Effects of Si alloying and T6 treatment on mechanical properties and wear resistance of ZA27 alloys

To improve the mechanical properties and wear resistance of ZA27 alloy, Si was introduced to the alloy, and the effect of Si alloying and T6 heat treatment on t

期刊

ZA27alloySialloyingmechanicalpropertieswearresistanceZA27 alloy Si alloy

Phase-field simulation of solidification dendritic segregation in Ti-45Al alloy

微观结构和 TiAl 合金的机械性质直接被连接到微分离它不能在团结期间被避免。那么彻底的理解微分离应该是大帮助进一步提高演员组产品的机械性质。理论分析和实验被用来预言

期刊

阶段地模型树枝状的分离Ti-45Al免费精力等温的团结TP391.92Aphase-field model dendritic segregati

Insulation effect of air cavity in sand mold using 3D printing technology

在 3D 包围起床人的空气洞的屏蔽效果打印了沙模子被学习。热流动上的空气洞的影响理论上被分析。结果证明在 3D 的空气洞的热流动打印了沙模子显著地不到结合树脂的沙的。在

期刊

On first-order theorem proving using generalized odd-superpositions Ⅱ

It is shown that the proof system using odd-superpositions Ⅱ is not complete.The reason leading to this incompleteness is that the use of idempotency rule is n

期刊

theoremprovingFIRST-ORDERPOLYNOMIALSodd-superpositionsⅡGENERALIZEDodd-sup

Morphology and defect structures of novel relaxor ferroelectric single crystals Pb(Mg1/3&

High-performance relaxor ferroelectric single crystals Pb(Mg1/3Nb2/3)O3-PbTiO3 have been grown successfully by a mod

期刊

relaxorFERROELECTRICSsinglecrystalsPMNTMORPHOLOGYdefectstructuresdomain

A polynomial-time algorithm for reducing the number of variables in MAX SAT problem

与本文相关的学术论文