关键词:SAT问题; 2-SAT子问题; 2-SAT算法
New SAT solver based on finding satisfiable 2-SAT sub problem
FU Yang-chun, ZHOU Yu-ren
(School of Computer Science & Engineering, South China University of Technology, Guangzhou 510006, China)
Abstract:Satisfiability (SAT) problem is one of the NP-Hard problems. This paper introduced a new SAT solver called FSSAT. This SAT solver solved the problem by searching a satisfiable 2-SAT sub problem. SAT was NP-complete, but it can be solved in linear time when the given formula contains only binary clauses (2-SAT).BinSat(2-SAT solver) was used to solve the 2-SAT sub problem and improved the 2-SAT sub problem according to the truth assignment. The experimental results show that the solver outperforms UnitWalk.
Key words:SAT problem; 2-SAT sub problem; 2-SAT solver
0 引言 ......