$\Pi_2^P$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
<|reference_start|>$\Pi_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 $\Pi_{2}^{P}$, 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 $\Pi_{2}^{P}$-complete.<|reference_end|>
@article{zhuk2024$\pi_{2}^{p}$,
    title={$\Pi_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint
  Satisfaction Problem},
    author={Dmitriy Zhuk},
    journal={arXiv preprint arXiv:2404.03844},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03844},
    primaryClass={cs.CC cs.LO math.LO}
}