| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427851 | Information Processing Letters | 2011 | 5 Pages |
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).
