Low-level dichotomy for quantified constraint satisfaction problems |
| |
Authors: | Barnaby Martin |
| |
Affiliation: | School of Engineering and Computing Sciences, Durham University, Science Labs, South Road, Durham DH1 3LE, UK |
| |
Abstract: | 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), 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 trivial) is a microcosm for all QCSPs. Specifically, for any B there exists a C — generally not a core — such that CSP(C) is trivial, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions. |
| |
Keywords: | Computational complexity Quantified constraints Alternating logtime |
本文献已被 ScienceDirect 等数据库收录! |
|