Quantified Constraint Satisfaction Problem on semicomplete digraphs

Đapić, Petar; Marković, Petar; Martin, Barnaby

Abstract

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.

Citation

Đapić, P., Marković, P., & Martin, B. (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic, 18(1), Article 2. https://doi.org/10.1145/3007899

• Journal Article Type: Article
• Acceptance Date: Oct 12, 2016
• Online Publication Date: Apr 13, 2017
• Publication Date: Apr 13, 2017
• Deposit Date: Oct 14, 2016
• Publicly Available Date: Oct 17, 2016
• Journal: ACM Transactions on Computational Logic
• Print ISSN: 1529-3785
• Electronic ISSN: 1557-945X
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 18
• Issue: 1
• Article Number: 2
• DOI: https://doi.org/10.1145/3007899
• Public URL: https://durham-repository.worktribe.com/output/1402851