Algorithmic Analysis on a Class of Boolean Equations

摘要：

Efficient procedures for satisfiability verification are foundations of numerical simulation and algorithmic analysis of NP-compIete problems. Previous researches in this direction include well-known Davis-Putnam-Logemann-Loveland (DPLL) and leaf removal procedures. In this paper, we propose a new procedure called Leaf-removal Gaussian Elimination procedure (LGC) to verify the satisfiability of a class of NP-compIete problems. This novel procedure is much simpler and faster than the original DPLL procedure. We also provide estimation of the phase transition point based on this procedure. Numerical experiments are conducted for Boolean equations systems with different parameters and the results verify the validity and efficiency of our novel techniques.

作者: Wei Wei Binghui Guo Hongbo Zhou Zhiming Zheng

作者单位: LMIB and School of Mathematics and Systems Science Beihang University Beijing, China Computer Science Department Southern Illinois University Carbondale IL, USA

会议类型: 国际会议

会议名称: The 2010 International Conference on Computer Application and System Modeling(2010计算机应用与系统建模国际会议 ICCASM 2010)

会议地点: 太原

会议语种:英文

页码: 170-173

在线出版日期: 2010-10-22（万方平台首次上网日期，不代表论文的发表时间）