Meditations on Quantified Constraint Satisfaction

Details Meditations on Quantified Constraint Satisfaction Meditations on Quantified Constraint Satisfaction

2012-01-30

arxiv.org/abs/1201.6306v1

Computer Science

Logic in Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Meditations on Quantified Constraint Satisfaction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Meditations on Quantified Constraint Satisfaction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Meditations on Quantified Constraint Satisfaction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-360292