The Library
Constraint satisfaction with counting quantifiers
Tools
Madelaine, Florent, Martin, Barnaby and Stacho, Juraj (2012) Constraint satisfaction with counting quantifiers. In: Computer Science – Theory and Applications: 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings. Lecture Notes in Computer Science, 7353 . Berlin Heidelberg: Springer Netherlands, pp. 253-265.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-30642-6_24
Abstract
We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCSPs).
We show that a single counting quantifier strictly between ∃ ≥ 1: = ∃ and ∃ ≥ n : = ∀ (the domain being of size n) already affords the maximal possible complexity of QCSPs (which have both ∃ and ∀), being Pspace-complete for a suitably chosen template.
Next, we focus on the complexity of subsets of counting quantifiers on clique and cycle templates. For cycles we give a full trichotomy – all such problems are in L, NP-complete or Pspace-complete. For cliques we come close to a similar trichotomy, but one class remains outstanding.
Afterwards, we consider the generalisation of CSPs in which we augment the extant quantifier ∃ ≥ 1: = ∃ with the quantifier ∃ ≥ j (j ≠ 1). Such a CSP is already NP-hard on non-bipartite graph templates. We explore the situation of this generalised CSP on bipartite templates, giving various conditions for both tractability and hardness – culminating in a classification theorem for general graphs.
Finally, we use counting quantifiers to solve the complexity of a concrete QCSP whose complexity was previously open.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Netherlands | ||||
Place of Publication: | Berlin Heidelberg | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Computer Science – Theory and Applications: 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | 7353 | ||||
Page Range: | pp. 253-265 | ||||
DOI: | 10.1007/978-3-642-30642-6_24 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |