A Development of LAF for Satisfying Assignments Search
Jiang Liu, Honghao Zhou · 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) · 2019
The l-in-3-SAT problem is one of the NP-complete problems. Recently, a new method named Linear Algebra Formulation (LAF) is proposed for l-in-3-SAT. In experiment, we find that this method is effective to handle the instances which are probably l-in-3 unsatisfiable. To deal with the l-in-3 satisfiable instances, this paper develops an efficient search method based on LAF. Certainly, this algorithm is not ensured to be complete. Nonetheless, the experiment shows that it is able to solve the majority of randomly generated instances with no more than 160 variables.