Quantified Valued Constraint Satisfaction Problem

We study the complexity of the quantified and valued extension of the constraint satisfaction problem (QVCSP) for certain classes of languages. This problem is also known as the weighted constraint satisfaction problem with min-max quantifiers [1]. The multimorphisms that preserve a language is the starting point of our analysis. We establish some situations where a QVCSP is solvable in polynomial time by formulating new algorithms or by extending the usage of collapsibility, a property well known for reducing the complexity of the quantified CSP (QCSP) from Pspace to NP. In contrast, we identify some classes of problems for which the VCSP is tractable but the QVCSP is Pspace-hard. As a main Corollary, we derive an analogue of Shaeffer's dichotomy between P and Pspace for QCSP on Boolean languages and Cohen et al. dichotomy between P and NP-complete for VCSP on Boolean valued languages: we prove that the QVCSP follows a dichotomy between P and Pspace-complete. Finally, we exhibit examples of NP-complete QVCSP for domains of size 3 and more, which suggest at best a trichotomy between P, NP-complete and Pspace-complete for the QVCSP.