The complexity of constraint satisfaction games and QCSP
The complexity of constraint satisfaction games and QCSP
复制标题
约束满足博弈和QCSP的复杂性
DOI：
10.1016/j.ic.2009.05.003
复制
发表时间：
2009
影响因子：
1
通讯作者：
Börner F
中科院分区：
文献类型：
--
作者：
Börner F
我们研究了两人约束满足博弈的复杂性。这种博弈的一个实例是由重叠变量集上的约束集合给出的，两个参与者交替移动，以指定的顺序将有限域中的值分配给变量。第一个参与者试图满足所有约束，而另一个参与者试图打破至少一个约束;目标是决定第一个参与者是否有获胜策略。我们表明，这样的游戏可以方便地表示由一个逻辑形式的量化约束满足，其中的一个实例是由一阶句子中的量词交替和量词自由的一部分是一个连接（正）原子公式，其目标是决定是否句子是真的。虽然决定这样一个游戏的问题一般是PSPACE-完全的，通过限制允许的约束谓词的集合，可以得到无限类的约束满足游戏的复杂性较低。我们使用量化的约束满足框架来研究如何决定这样一个游戏的复杂性取决于允许谓词的参数集。对于每个谓词，可以关联某些谓词保留操作，称为多态性。我们表明，我们的游戏的复杂性是由满射多态性的约束谓词。我们说明了如何使用这个结果，通过识别各种各样的约束满足游戏的复杂性。
We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true. While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.
登录
查看更多内容
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Hubie Chen
通讯作者：
Hubie Chen
DOI：
--
发表时间：
1979
期刊：
影响因子：
--
作者：
R. Pöschel;L. A. Kalužnin
通讯作者：
L. A. Kalužnin
组合游戏的复杂性、吸引力和挑战
影响因子：
1.1
作者：
A. Fraenkel
通讯作者：
A. Fraenkel
关于一些两人完美信息博弈的复杂性
DOI：
--
发表时间：
1978
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
T. Schaefer
通讯作者：
T. Schaefer
DOI：
--
发表时间：
2004
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
Hubie Chen
通讯作者：
Hubie Chen