Logic transformation and coding theory-based frameworks for Boolean satisfiabilityDhiraj Pradhan, Logic transformation and coding theory-based frameworks for Boolean satisfiability. Eighth IEEE International High-Level Design Validation and Test Workshop, 2003. . ISBN 0-7803-8236-6, pp. 57–62. December 2003. PDF, 342 Kbytes.
This paper proposes a new framework to the solution of Boolean Satisfiability. The first approach is based on certain structural analysis using circuit representation. Here, we convert the given CNF into multilevel circuits based on testability-driven transformation and optimization, and then apply a test technique developed by the authors to verify SAT. This test technique is based on the concepts developed by an earlier-proposed verification tool, VERILAT. Certain algebraic coding theory results are then derived that provide a lower bound on the number of solutions to SAT problems. These proposed frameworks have a real potential for providing new theoretical insights.