Meditations on quantified constraint satisfaction

DOI10.1007/978-3-642-29485-3_4MaRDI QIDQ2897943zbMATH OpenOpenAlexFDO

Authors Hubie Chen

Publication date 16 July 2012

Published in Logic and Program Semantics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.6306

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Analysis of algorithms and problem complexity (68Q25)

Abstract: The quantified constraint satisfaction problem (QCSP) is the problem of deciding, given a structure and a first-order prenex sentence whose quantifier-free part is the conjunction of atoms, whether or not the sentence holds on the structure. One obtains a family of problems by defining, for each structure B, the problem QCSP(B) to be the QCSP where the structure is fixed to be B. In this article, we offer a viewpoint on the research program of understanding the complexity of the problems QCSP(B) on finite structures. In particular, we propose and discuss a group of conjectures; throughout, we attempt to place the conjectures in relation to existing results and to emphasize open issues and potential research directions.

Recommendations

• Relatively quantified constraint satisfaction
• Existentially restricted quantified constraint satisfaction
• STACS 2005
• Quantified constraint satisfaction on monoids
• Computer Science Logic

Cited in

(28)

• Existentially restricted quantified constraint satisfaction
• Relatively quantified constraint satisfaction
• Low-level dichotomy for quantified constraint satisfaction problems
• The size of generating sets of powers
• Solving quantified constraint satisfaction problems
• Extending the notion of preferred explanations for quantified constraint satisfaction problems
• The constraint satisfaction problem and universal algebra
• Beyond Q-resolution and prenex form: a proof system for quantified constraint satisfaction
• QCSP on partially reflexive forests
• On the complexity of the model checking problem
• scientific article; zbMATH DE number 6519660 (Why is no real title available?)
• Collapsibility in Infinite-Domain Quantified Constraint Satisfaction
• Constraint satisfaction, irredundant axiomatisability and continuous colouring
• Asking the Metaquestions in Constraint Tractability
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Quantified Constraints in Twenty Seventeen
• The complexity of quantified constraints using the algebraic formulation
• Tractability of quantified temporal constraints to the max
• Quantified constraint satisfaction problem on semicomplete digraphs
• Quantified constraint satisfaction on monoids
• Computer Science Logic
• Learnability of solutions to conjunctive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Constraint satisfaction problem: what makes the problem easy
• Quantaloidal approach to constraint satisfaction
• _2P vs PSpace dichotomy for the quantified constraint satisfaction problem
• The complexity of constraint satisfaction games and QCSP

This page was built for publication: Meditations on quantified constraint satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897943)