Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Recognizing frozen variables in constraint satisfaction problems.

Jonsson, P. and Krokhin, A. (2004) 'Recognizing frozen variables in constraint satisfaction problems.', Theoretical computer science., 329 (1-3). pp. 93-113.

Abstract

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances. We show that the complexity of such problems is determined by certain algebraic properties of these relations. Under the assumption that NP≠coNP (and consequently PTIME≠NP), we characterize all tractable problems, and describe large classes of NP-complete, coNP-complete, and DP-complete problems. As an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2; and (2) when all unary relations are present. We also give a rough classification for domain size 3.

Item Type:Article
Keywords:Constraint satisfaction, Frozen variable, Computational complexity, Polymorphism.
Full text:PDF - Accepted Version (325Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.tcs.2004.08.006
Record Created:29 Mar 2010 12:05
Last Modified:14 Dec 2011 09:54

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