Publication details for Dr Barnaby MartinĐapić, Petar, Marković, Petar & Martin, Barnaby (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic 18(1): 2.
- Publication type: Journal Article
- ISSN/ISBN: 1529-3785, 1557-945X
- DOI: 10.1145/3007899
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(H) is either in P, is NP-complete, or is Pspace-complete. The largest part of our work is the algebraic classification of precisely which semicomplete digraphs enjoy only essentially unary polymorphisms, which is combinatorially interesting in its own right.