Algorithmic and complexity results for boolean and pseudo-boolean functions

OF THE DISSERTATION Algorithmic and Complexity Results for Boolean and Pseudo-Boolean Functions by Aritanan G. Gruber Dissertation Director: Endre Boros This dissertation presents our contributions to two problems. In the first problem, we study the hardness of approximation of clause minimum and literal minimum representations of pure Horn functions in n Boolean variables. We show that unless P = NP, it is not possible to approximate in polynomial time the minimum number of clauses and the minimum number of literals of pure Horn CNF representations to within a factor of 2log 1−o(1) n. This is the case even when the inputs are restricted to pure Horn 3-CNFs with O(n1+e) clauses, for some small positive constant e. Furthermore, we show that even allowing sub-exponential time computation, it is still not possible to obtain constant factor approximations for such problems unless the Exponential Time Hypothesis is false. In the second problem, we study quadratizations of pseudo-Boolean functions, that is, transformations that given a pseudo-Boolean function f(x) in n variables, produce a quadratic pseudo-Boolean function g(x, y) in n+m variables such that f(x) = miny∈{0,1}m g(x, y) for all x ∈ {0, 1}n. We present some new termwise procedures, leading to improved experimental results, and then take a global perspective and start a systematic investigation of some structural properties of the class of all quadratizations of a given function.