2012 | OriginalPaper | Buchkapitel
Constraint Satisfaction with Counting Quantifiers
verfasst von : Florent Madelaine, Barnaby Martin, Juraj Stacho
Erschienen in: Computer Science – Theory and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.