Quantified constraints: Algorithms and complexity
UNSPECIFIED (2003) Quantified constraints: Algorithms and complexity. In: 12th Annual Conference of the European-Association-for-Computer-Logic/8th Kurt Godel Colloquium/17th International Workshop on Computer Science Logic, VIENNA UNIV TECHNOL, VIENNA, AUSTRIA, AUG 25-30, 2003. Published in: COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2803 pp. 58-70.Full text not available from this repository.
The standard constraint satisfaction problem over an arbitrary finite domain can be expressed as follows: given a first-order sentence consisting of a conjunction of predicates, where all of the variables are existentially quantified, determine whether the sentence is true. This problem can be parameterized by the set of allowed constraint predicates. With each predicate, one can associate certain predicate-preserving operations, called polymorphisms, and the complexity of the parameterized problem is known to be determined by the polymorphisms of the allowed predicates. In this paper we consider a more general framework for constraint satisfaction problems which allows arbitrary quantifiers over constrained variables, rather than just existential quantifiers. We show that the complexity of such extended problems is determined by the surjective polymorphisms of the constraint predicates. We give examples to illustrate how this result can be used to identify tractable and intractable cases for the quantified constraint satisfaction problem over arbitrary finite domains.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||COMPUTER SCIENCE LOGIC, PROCEEDINGS|
|Editor:||Baaz, M and Makowsky, JA|
|Number of Pages:||13|
|Page Range:||pp. 58-70|
|Title of Event:||12th Annual Conference of the European-Association-for-Computer-Logic/8th Kurt Godel Colloquium/17th International Workshop on Computer Science Logic|
|Location of Event:||VIENNA UNIV TECHNOL, VIENNA, AUSTRIA|
|Date(s) of Event:||AUG 25-30, 2003|
Actions (login required)