The Library
Quantified constraints: Algorithms and complexity
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, VIENNA UNIV TECHNOL, VIENNA, AUSTRIA, AUG 25-30, 2003. Published in: COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2803 pp. 58-70. ISBN 3-540-40801-0. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
Official Date: | 2003 | ||||
Dates: |
|
||||
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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |