Boolean Satisfiability Problem: Discrete and Continuous Reformulations with Applications
Оксана Сергеевна Пичугина, Olha Matsyi · 2020 IEEE 15th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET) · 2020
An SAT problem is attacked, which is one of the most fundamental problems in Computer Science. A number of algebraic reformulations of SAT are presented as problems of Boolean and continuous optimization. They are based on applying jointly theories of convex extensions of functions, functional continuous representations of sets, and Euclidean combinatorial configurations. This results in the possibility of applying powerful tools of discrete and continuous optimization, including convex, to the exact solution of SAT and approximate one with error estimate evaluation.