A Proposed SAT Algorithm

Dr. Bagais A., Junaidu S. B., Abdullahi M.

Volume 13 Issue 1

Global Journal of Computer Science and Technology

This paper reviews existing SAT algorithms and proposes a new algorithm that solves the SAT problem.The proposed algorithm differs from existing algorithms in several aspects. First, the proposed algorithm does not do any backtracking during the searching process that usually consumes significant time as it is the case with other algorithms.Secondly, the searching process in the proposed algorithm is simple, easy to implement, and each step is determined instantly unlike other algorithms where decisions are made based on some heuristics or random decisions. For clauses with three literals, the upper bound for the proposed algorithm is O(1.8171n). While some researchers reported better upper bounds than this, those upper bounds depend on the nature of the clauses while our upper bound is independent of the nature of the propositional formula.