• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Algorithmic and complexity results for Boolean and pseudo-Boolean functions.
【24h】

Algorithmic and complexity results for Boolean and pseudo-Boolean functions.

机译：布尔和伪布尔函数的算法和复杂度结果。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：本文提出了我们对两个问题的贡献。在第一个问题中，我们研究了n个布尔变量中纯Horn函数的子句最小值和文字最小值表示的逼近度。我们证明，除非P = NP，否则不可能在多项式时间内将纯Horn CNF表示形式的子句的最小数量和字面量的最小数量近似为2log1-o（1）n。即使对于某些较小的正常数epsilon，即使将输入限制为带有O（n1 + epsilon）子句的纯Horn 3-CNF，也是如此。此外，我们表明，即使允许进行次指数时间计算，除非指数时间假设为假，否则仍无法获得此类问题的常数因子近似值。在第二个问题中，我们研究伪布尔函数的二次化，即即，在n个变量中给定伪布尔函数ƒ（x）的转换，在n + m个变量中产生二次伪布尔函数g（x，y），使得ƒ（x）= miny∈{0,1}所有x∈{0,1} n的mg（x，y）。我们提出了一些新的术语过程，从而改善了实验结果，然后从全局的角度出发，开始对给定函数的所有二次化的类的某些结构性质进行系统研究。;我们证明了n中的所有伪布尔函数变量可以分别具有最多O（2n / 2）和O2n n log n个辅助变量的平方和y线性平方（不包含仅涉及辅助变量的二次乘积），并且几乎所有这些函数都需要O（2n / 2）和O（2n / n）辅助变量分别在任何平方和任何y线性平方中。对于度d伪布尔函数的求平方，我们获得了边界O（nd / 2）和O（nd / 2），对于y线性求平方，我们得到了n-2和O（n / log n）的边界（和对称伪布尔函数的O（√n）求平方）。我们所有的上限都是有建设性的，因此它们提供了新的（y-线性）平方化算法;然后​​，我们对带有一个辅助变量的负单项式的所有平方化的集合进行了特征化，结果令人惊讶地难以获得，并且目前的证据相当漫长而复杂。

著录项

  • 作者

    Gruber, Aritanan G.;

  • 作者单位

    Rutgers The State University of New Jersey - New Brunswick.;

  • 授予单位 Rutgers The State University of New Jersey - New Brunswick.;
  • 学科 Operations Research.;Computer Science.;Applied Mathematics.
  • 学位 Ph.D.
  • 年度 2015
  • 页码 206 p.
  • 总页数 206
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号