Reducing a 3-SAT Instance to a Set of 2-SAT Instances Using the Idea of Set Covering Problem
Sardar Anisul Haque, Ali Jaoua, Jihad M. Al Ja'am, Hafeez Ur Rehman · 2023
This paper describes a novel algorithm that enumerates a set of Boolean variables from a 3-SAT instance such that for any truth assignments, it will be reduced to a 2-SAT instance or an empty formula or a formula with one or more empty clauses. We showed that the set of Boolean variables of interest can be found by formulating the given 3-SAT instance into an instance of set covering problem.