Low-level dichotomy for Quantified Constraint Satisfaction Problems

Details Low-level dichotomy for Quantified Constraint Satisfaction Problems Low-level dichotomy for Quantified Constraint Satisfaction Problems

2011-02-17

arxiv.org/abs/1102.3463v1

Computer Science

Computational Complexity

Scientific paper

Building on a result of Larose and Tesson for constraint satisfaction problems (CSP s), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime. We show that the class of B such that CSP(B) is first-order expressible (indeed, trivially true) is a microcosm for all QCSPs. Specifically, for any B there exists a C such that CSP(C) is trivially true, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions.

Affiliated with

Also associated with

No associations

Rating

Low-level dichotomy for Quantified Constraint Satisfaction Problems 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 Low-level dichotomy for Quantified Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-level dichotomy for Quantified Constraint Satisfaction Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-379887