Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/3302| Title: | Quantified constraint satisfaction problem on semicomplete digraphs | Authors: | Đapić, Petar Marković, Petar Martin B. |
Issue Date: | 1-Apr-2017 | Journal: | ACM Transactions on Computational Logic | Abstract: | © 2017 ACM. We study the (non-uniform) quantified constraint satisfaction problem QCSP(ℋ)asH ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(ℋ) 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. | URI: | https://open.uns.ac.rs/handle/123456789/3302 | ISSN: | 15293785 | DOI: | 10.1145/3007899 |
| Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
4
checked on May 10, 2024
Page view(s)
18
Last Week
6
6
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.