Elliptic approximations of propositional formulae
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.
primary 68q25 90c09 secondary 90c10 90c27