Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

The complexity of constraint satisfaction games and QCSP.

Boerner, F. and Bulatov, A. and Chen, H. and Jeavons, P. and Krokhin, A. (2009) 'The complexity of constraint satisfaction games and QCSP.', Information and computation., 207 (9). pp. 923-944.

Abstract

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.

Item Type:Article
Keywords:Constraint satisfaction, Games, Quantified constraint satisfaction problem, Polymorphisms, Complexity, Algorithms.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.ic.2009.05.003
Record Created:15 Dec 2009 11:50
Last Modified:05 Jan 2010 11:07

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library