The Library
Quantified constraints: Algorithms and complexity
Tools
Tools
Tools
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, AUG 25-30, 2003, VIENNA UNIV TECHNOL, VIENNA, AUSTRIA.
Full text not available from this repository.Abstract
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 |
| Publisher: | SPRINGER-VERLAG BERLIN |
| ISBN: | 3-540-40801-0 |
| ISSN: | 0302-9743 |
| Editor: | Baaz, M and Makowsky, JA |
| Date: | 2003 |
| Volume: | 2803 |
| Number of Pages: | 13 |
| Page Range: | pp. 58-70 |
| Publication Status: | Published |
| 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 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/9212 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
