Đapić, Petar and Marković, Petar and Martin, Barnaby (2017) 'Quantified constraint satisfaction problem on semicomplete digraphs.', ACM transactions on computational logic., 18 (1). p. 2.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (534Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1145/3007899 |
| Publisher statement: | © 2017 ACM. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic, 18, 1, Article 2 (April 2017), https://doi.org/10.1145/3007899. |
| Date accepted: | 12 October 2016 |
| Date deposited: | 17 October 2016 |
| Date of first online publication: | 13 April 2017 |
| Date first made open access: | 13 April 2017 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
