Low-level dichotomy for quantified constraint satisfaction problems


Martin, B. 2011. Low-level dichotomy for quantified constraint satisfaction problems. Information Processing Letters. 111 (20), pp. 999-1003. https://doi.org/10.1016/j.ipl.2011.07.010
TitleLow-level dichotomy for quantified constraint satisfaction problems
AuthorsMartin, B.

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.

Research GroupFoundations of Computing group
JournalInformation Processing Letters
Publication dates
Print31 Oct 2011
Online21 Jul 2011
Publication process dates
Deposited20 Dec 2012
Accepted11 Jul 2011
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1016/j.ipl.2011.07.010
Permalink -


  • 19
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as