Elliptic approximations of propositional formulae Original Research Article

A propositional formula can be approximated by a concave quadratic function. This approximation is obtained as a second-order Taylor expansion of a concave smooth model. It is shown that in the 3-SAT case, the involved parameters can be set to such values that yield optimal discriminative properties. Two concentric (generally elliptic) quadratic convex regions are established, the inner one containing only satisfiable assignments and the outer one excluding the average non-satisfiable assignment and including all satisfiable assignments.