Algorithmic analysis on a class of Boolean equations

Wei Wei, Binghui Guo, Hongbo Zhou, Zhiming Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Efficient procedures for satisfiability verification are foundations of numerical simulation and algorithmic analysis of NP-complete 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-complete 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.

Original languageEnglish
Title of host publicationICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings
PagesV12170-V12173
DOIs
StatePublished - 6 Dec 2010
Event2010 International Conference on Computer Application and System Modeling, ICCASM 2010 - Shanxi, Taiyuan, China
Duration: 22 Oct 201024 Oct 2010

Publication series

NameICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings
Volume12

Conference

Conference2010 International Conference on Computer Application and System Modeling, ICCASM 2010
CountryChina
CityShanxi, Taiyuan
Period22/10/1024/10/10

Fingerprint Dive into the research topics of 'Algorithmic analysis on a class of Boolean equations'. Together they form a unique fingerprint.

  • Cite this

    Wei, W., Guo, B., Zhou, H., & Zheng, Z. (2010). Algorithmic analysis on a class of Boolean equations. In ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings (pp. V12170-V12173). [5622117] (ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings; Vol. 12). https://doi.org/10.1109/ICCASM.2010.5622117