一种新的SAT问题预处理算法

A New Algorithm for SAT Preprocessing

提出了一项新的正向推理技术:对称扩展的一元子句推导(Symmetric Extended Unit Propagation)。与传统的一元子句推导技术相比,文中的方法通过在一元子句推导过程中添加对称的蕴涵关系从而能够推导出更多的一元子句。基于这项新技术实现了一个可满足性问题(SAT)预处理器Snowball。实验结果验证了该项技术的有效性,表明该预处理器Snowball能够有效地化简SAT问题的规模并减少解决SAT问题的时间。

In this paper we propose a new forward reasoning technique called Symmetric Extended Unit Propagation （SEUP）. Compared to the ordinary UP our method can deduce more unit literals through adding the symmetric implications during unit propagating literals. A SAT preprocessor Snowball is implemented based on this new technique. Experimental results verify the efficiency of this new technique and show that Snowball can generously reduce the overall runtime in solving SAT problems.