SAT问题子句消去法快速求解

A Fast Solution for SAT Problem based on Clause Elimination Method

布尔可满足性问题(SAT)是最基本的NPC问题,直接涉及到集成电路设计优化、生物基因、人工智能、互联网等诸多领域的快速计算。给出了一种子句消去法,运用限位数、子句块和关联段等概念,探索出了用确定法则快速求出SAT满足解的计算方法,为纯离散变量计算找到了一种新途径。

Boolean satisfaction problem(SAT)is one of the fundamental problems that was proven to beNP-complete,which involves obtaining fast solution for various fields including integrated circuit designand optimization,biological gene,artificial intelligence and Internet.By using the concepts includingFix-bit number,Clause-block and Relate-section,a clause elimination method is discovered using thedetermination rule that aims at rapidly obtaining satisfied solution for SAT.A new way is found out for thesolution of pure discrete variables.