Low-level dichotomy for quantified constraint satisfaction problems

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

► New dichotomy theorem for the quantified constraint satisfaction problem.
► If BB is a core, then QCSP(B)QCSP(B) is either in ALogtimeALogtime or is LL-hard.
► New microcosm theorem for quantified constraint satisfaction problems (QCSPs).
► All the complexity-theoretic richness of QCSPs already exists in templates that are c-valid (whose CSP is trivial).