Constraint Satisfaction with Counting Quantifiers
Constraint Satisfaction with Counting Quantifiers
复制标题
计数量词的约束满足
DOI：
10.1137/140981332
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Stacho
中科院分区：
文献类型：
--
作者：
Barnaby Martin;Florent R. Madelaine;J. Stacho
我们在存在计数量词 $\exists^{\geq j}$ 的情况下开始研究约束满足问题（CSP），该计数量词断言至少存在 $j$ 元素，使得随后的属性成立。这些是量化 CSP (QCSP) 模型中 CSP 的自然变体。即 $\exists^{\geq 1}:=\exists$ 和 $\exists^{\geq n}:=\forall$ （对于大小为 $n$ 的域）。我们观察到，严格介于 $\exists$ 和 $\forall$ 之间的单个计数量词 $\exists^{\geq j}$ 已经提供了 QCSP 的最大可能复杂性（同时具有 $\exists$ 和 $\forall$），即对于适当选择的模板来说是 Pspace-complete。因此，为了更好地理解这个问题的复杂性，我们重点关注有限的情况，并得出以下结果。首先，对于团和循环模板上计数量词的所有子集，我们给出完整的三分法——所有此类问题都在 P、NP 完全或 P 空间完全中。其次，我们考虑两个量词的问题：...
We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers $\exists^{\geq 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, $\exists^{\geq 1}:=\exists$ and $\exists^{\geq n}:=\forall$ (for the domain of size $n$). We observe that a single counting quantifier $\exists^{\geq j}$ strictly between $\exists$ and $\forall$ already affords the maximal possible complexity of QCSPs (which have both $\exists$ and $\forall$), 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: ...
约束满足博弈和QCSP的复杂性
影响因子：
1
作者：
Börner F
通讯作者：
Börner F