Algorithmic analysis on a class of Boolean equations

Wei Wei, Binghui Guo, Hongbo Zhou, Zhiming Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-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
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

Computational complexity
Phase transitions
Computer simulation
Leaves
NP-complete problem
Verify
Experiments
Gaussian elimination
Class
Phase Transition
Numerical Experiment
Numerical Simulation

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 [5622117] (ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings; Vol. 12). https://doi.org/10.1109/ICCASM.2010.5622117
Wei, Wei ; Guo, Binghui ; Zhou, Hongbo ; Zheng, Zhiming. / Algorithmic analysis on a class of Boolean equations. ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings. 2010. (ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings).
@inproceedings{b46c487efa554823aabf94e3ee3433a8,
title = "Algorithmic analysis on a class of Boolean equations",
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.",
author = "Wei Wei and Binghui Guo and Hongbo Zhou and Zhiming Zheng",
year = "2010",
month = "12",
day = "6",
doi = "10.1109/ICCASM.2010.5622117",
language = "English",
isbn = "9781424472369",
series = "ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings",
booktitle = "ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings",

}

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., 5622117, ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings, vol. 12, 2010 International Conference on Computer Application and System Modeling, ICCASM 2010, Shanxi, Taiyuan, China, 22/10/10. https://doi.org/10.1109/ICCASM.2010.5622117

Algorithmic analysis on a class of Boolean equations. / Wei, Wei; Guo, Binghui; Zhou, Hongbo; Zheng, Zhiming.

ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings. 2010. 5622117 (ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings; Vol. 12).

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

TY - GEN

T1 - Algorithmic analysis on a class of Boolean equations

AU - Wei, Wei

AU - Guo, Binghui

AU - Zhou, Hongbo

AU - Zheng, Zhiming

PY - 2010/12/6

Y1 - 2010/12/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78649586755&partnerID=8YFLogxK

U2 - 10.1109/ICCASM.2010.5622117

DO - 10.1109/ICCASM.2010.5622117

M3 - Conference contribution

SN - 9781424472369

T3 - ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings

BT - ICCASM 2010 - 2010 International Conference on Computer Application and System Modeling, Proceedings

ER -

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