| 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 2log1--o(1)n. This is the case even when the inputs are restricted to pure Horn 3-CNFs with O(n1+epsilon) clauses, for some small positive constant epsilon. 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 ƒ( x) in n variables, produce a quadratic pseudo-Boolean function g(x,y) in n + m variables such that ƒ(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.;We show that all pseudo-Boolean functions in n variables can be quadratized and y-linear quadratized (no quadratic products involving solely auxiliary variables) with at most O(2n/2) and O2n n log n auxiliary variables, respectively, and that almost all those functions require O(2n/2) and O(2n/n) auxiliary variables in any quadratization and any y-linear quadratization, respectively. We obtain the bounds O(n d/2) and O(nd/2) for quadratizations of degree-d pseudo-Boolean functions, and bounds of n -- 2 and O(n/log n) for y-linear quadratizations (and O(√ n) for quadratizations) of symmetric pseudo-Boolean functions. All our upper bounds are constructive, so they provide new (y-linear) quadratization algorithms.;We then finish with a characterization of the set of all quadratizations of negative monomials with one auxiliary variable, a result that was surprisingly difficult to obtain, and whose proof at the moment is rather long and intricate. |
