online read us now
Paper details
Number 2 - June 2014
Volume 24 - 2014
Selection of search strategies for solving 3-SAT problems
Andrzej Pułka
Abstract
The paper concerns the problem of Boolean satisfiability checking, which is recognized as one of the most important issues
in the field of modern digital electronic system verification and design. The paper analyzes different strategies and scenarios
of the proving process, and presents a modified and extended version of the author’s FUDASAT algorithm. The original
FUDASAT methodology is an intuitive approach that employs a commonsense reasoning methodology. The main objective
of the work is to investigate the SAT-solving process and try to formulate a set of rules controlling the reasoning process of
the FUDASAT inference engine. In comparison with the author’s previous works, the paper introduces new mechanisms:
hypergraph analysis, multiple variable assignments and search space pruning algorithms. The approach considers only 3-SAT class functions, although a generalization of the method is discussed as well. The presented approach has been tested
on various benchmarks and compared with the original pure FUDASAT algorithm as well as with other algorithms known
from the literature. Finally, the benefits of the proposed SAT solving technique are summarized.
Keywords
SAT solving, formal verification, CNF, Boolean satisfiability