$\prod_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem

The Quantified Constraint Satisfaction Problem is the problem of evaluating a sentence with both quantifiers, over relations from some constraint language, with conjunction as the only connective. We show that for any constraint language on a finite domain the Quantified Constraint Satisfaction Problem is either in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Pi_{2}^{P}$</tex>, or PSpace-complete. Additionally, we build a constraint language on a 6-element domain such that the Quantified Constraint Satisfaction Problem over this language is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Pi_{2}^{P}$</tex> -complete.