Algorithmic analysis on a class of Boolean equations

Wei Wei, Binghui Guo, Hongbo Zhou, Zhiming Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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
PublisherIEEE Computer Society
Pages170-173
Number of pages4
ISBN (Print)9781424472369
DOIs
StatePublished - 2010

Publication series

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

Fingerprint

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

Cite this