2011/02/17 by Barnaby Martin, Martin, Barnaby
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.1102.3463
arxiv created 2011/02/17 · arxiv updated 2011/02/18
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.