首页> 外文会议>Automata, languages and programming >A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
【24h】

A Fast and Simple Parallel Algorithm for the Monotone Duality Problem

机译:解决单调对偶问题的快速简单并行算法

获取原文
获取原文并翻译 | 示例

摘要

We consider the monotone duality problem i.e., checking whether given monotone CNF φ and DNF ψ are equivalent, which is a prominent open problem in NP-completeness. We construct a fast and simple parallel algorithms for the problem, that run in polylogarithmic time by using quasi-polynomially many processors. The algorithm exhibits better parallel time complexity of the existing algorithms of El-bassioni [11]. By using a different threshold of the degree parameter e of φin the algorithm, we also present a stronger bound on the number of processors for polylogarithmic-time parallel computation and improves over the previously best known bound on the sequential time complexity of the problem in the case when the magnitudes of |φ|, |φ| and n are different, e.g., |ψ| = |φ|~α n for α > 1, where n denotes the number of variables. Furthermore, we show that, for several interesting well-known classes of monotone CNFs φ such as bounded degree, clause-size, and intersection-size, our parallel algorithm runs polylogarithmic time by using polynomially many processors.
机译:我们考虑单调对偶性问题,即检查给定的单调CNFφ和DNFψ是否相等,这是NP完整性中一个突出的开放问题。我们针对该问题构造了一种快速,简单的并行算法,该算法通过使用拟多项式许多处理器在多对数时间内运行。该算法展现了现有的El-bassioni算法更好的并行时间复杂度[11]。通过在算法中使用φ的度数参数e的不同阈值,我们还为多对数时间并行计算提供了更强的处理器数量界限,并改善了问题中顺序时间复杂度方面先前已知的界限。 |φ|,|φ|的大小的情况和n不同,例如|ψ| = |φ|〜α>> n对于α> 1,其中n表示变量数。此外,我们显示出,对于一些有趣的众所周知的单调CNF类别,例如有界度,子句大小和交集大小,我们的并行算法通过使用多项式多个处理器来运行对数时间。

著录项

  • 来源
  • 会议地点 Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR);Rhodes(GR)
  • 作者

    Endre Boros; Kazuhisa Makino;

  • 作者单位

    RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003;

    Department of Mathematical Informatics, University of Tokyo, Tokyo, 113-8656, Japan;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 程序设计、软件工程;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号