Quantified constraints: Algorithms and complexity
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 param...
| Hlavní autoři: | , , , |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
2003
|
| _version_ | 1826305874610618368 |
|---|---|
| author | Borner, F Bulatov, A Jeavons, P Krokhin, A |
| author_facet | Borner, F Bulatov, A Jeavons, P Krokhin, A |
| author_sort | Borner, F |
| collection | OXFORD |
| description | 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. © Springer-Verlag Berlin Heidelberg 2003. |
| first_indexed | 2024-03-07T06:39:28Z |
| format | Journal article |
| id | oxford-uuid:f8c3e620-f41c-444d-a431-f2d76e8aa175 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:39:28Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:f8c3e620-f41c-444d-a431-f2d76e8aa1752022-03-27T12:52:53ZQuantified constraints: Algorithms and complexityJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f8c3e620-f41c-444d-a431-f2d76e8aa175EnglishSymplectic Elements at Oxford2003Borner, FBulatov, AJeavons, PKrokhin, AThe 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. © Springer-Verlag Berlin Heidelberg 2003. |
| spellingShingle | Borner, F Bulatov, A Jeavons, P Krokhin, A Quantified constraints: Algorithms and complexity |
| title | Quantified constraints: Algorithms and complexity |
| title_full | Quantified constraints: Algorithms and complexity |
| title_fullStr | Quantified constraints: Algorithms and complexity |
| title_full_unstemmed | Quantified constraints: Algorithms and complexity |
| title_short | Quantified constraints: Algorithms and complexity |
| title_sort | quantified constraints algorithms and complexity |
| work_keys_str_mv | AT bornerf quantifiedconstraintsalgorithmsandcomplexity AT bulatova quantifiedconstraintsalgorithmsandcomplexity AT jeavonsp quantifiedconstraintsalgorithmsandcomplexity AT krokhina quantifiedconstraintsalgorithmsandcomplexity |