Algorithmic and complexity results for boolean and pseudo-boolean functions
Algorithmic and complexity results for boolean and pseudo-boolean functions
复制标题
布尔函数和伪布尔函数的算法和复杂性结果
DOI：
10.7282/t3pz5bhq
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Aritanan Gruber
中科院分区：
文献类型：
--
作者：
Aritanan Gruber
布尔函数和伪布尔函数的数学和复杂性结果。Gruber博士论文主任：Endre Boros这篇论文提出了我们对两个问题的贡献。在第一个问题中，我们研究了纯Horn函数在n个布尔变量中的子句最小表示和文字最小表示的逼近困难性。我们证明，除非P = NP，否则不可能在多项式时间内将纯Horn CNF表示的最小子句数和最小文字数近似到2log 1−o（1）n的因子内。即使输入被限制为具有O（n1+e）子句的纯Horn 3-CNF，对于一些小的正常数e，情况也是如此。此外，我们表明，即使允许次指数时间计算，它仍然是不可能的，以获得常数因子近似的问题，除非指数时间假设是假的。在第二个问题中，我们研究了伪布尔函数的二次化，即给定一个n元伪布尔函数f（x）的变换，生成一个n+m元二次伪布尔函数g（x，y），使得f（x）= miny∈{0，1} mg（x，y），对所有x ∈ {0，1}n.我们提出了一些新的termwise程序，导致改进的实验结果，然后采取全球性的角度来看，并开始系统的调查一类的所有平方一个给定的功能的一些结构特性。
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.