...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >CONSTRAINT SATISFACTION WITH COUNTING QUANTIFIERS
【24h】

CONSTRAINT SATISFACTION WITH COUNTING QUANTIFIERS

机译：约束与计数量化器的满足

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

摘要

We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers there exists >= j which assert the existence of at least j elements such that the ensuing property holds. These are natural variants of CSPs in the mould of quantified CSPs (QCSPs). Namely,there exists >= 1 := there exists and there exists >= n := for all (for the domain of size n). We observe that a single counting quantifier there exists >= j strictly between there exists and for all already affords the maximal possible complexity of QCSPs (which have both there exists and for all), namely, being Pspace-complete for a suitably chosen template. Therefore, to better understand the complexity of this problem, we focus on restricted cases for which we derive the following results. First, for all subsets of counting quantifiers on clique and cycle templates, we give a full trichotomy-all such problems are in P, NP-complete, or Pspace-complete. Second, we consider the problem with exactly two quantifiers: there exists >= 1 := there exists and there exists >= j (j not equal 1). Such a CSP is already NP-hard on nonbipartite graph templates. We explore the situation of this generalized CSP on graph templates, giving various conditions for both tractability and hardness. For quantifiers there exists >= 1 and there exists >= 2, we give a dichotomy for all graphs, namely, the problem is NP-hard if the graph contains a triangle or has girth at least 5, and is in P otherwise. We strengthen this result in the following two ways. For bipartite graphs, the problem is in P for forests and graphs of girth 4, and is Pspace-hard otherwise. For complete multipartite graphs, the problem is in L, NP-complete, or Pspace-complete. Finally, using counting quantifiers we solve the complexity of a concrete QCSP whose complexity was previously open.
机译：我们在存在数量≥的数量词存在的情况下启动对约束满足问题（CSP）的研究，该数量词=> j断言至少存在j个元素，从而确保了随后的性质成立。这些是定量CSP（QCSP）模型中CSP的自然变体。即，对于所有（对于大小为n的域），存在> = 1：=存在，并且存在> = n：=。我们观察到，存在一个单独的计数量词，在它们之间严格存在> = j，对于所有已经提供的QCSP，其最大可能的复杂度（既存在又对于所有QCSP），即对于适当选择的模板而言，其Pspace完全。因此，为了更好地理解此问题的复杂性，我们集中在有限的情况下，得出以下结果。首先，对于集团和周期模板上所有计数限定词的子集，我们给出了一个完整的三分法-所有这些问题都存在于P，NP完全或Pspace完全中。其次，我们考虑恰好有两个量词的问题：存在> = 1：=存在，并且存在> = j（j不等于1）。这样的CSP在非二分图模板上已经是NP-hard了。我们在图形模板上探索了这种广义CSP的情况，为可延展性和硬度提供了各种条件。对于量词，存在> = 1且存在> = 2，我们对所有图进行二分法，即，如果图包含三角形或围长至少为5，则问题为NP-难，否则为P。我们通过以下两种方式来增强此结果。对于二部图，问题出在森林和围长为4的图中的P中，否则为Pspace-hard。对于完整的多部分图，问题出在L，NP完全或Pspace完全。最后，使用计数量词，我们解决了一个具体的QCSP的复杂性，该复杂性以前是开放的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号