Journal article
QCSP on reflexive tournaments
- Abstract:
- We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components H1,…,Hn so that there exists an edge from every vertex of Hi to every vertex of Hj if and only if i < j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 646.0KB, Terms of use)
-
- Publisher copy:
- 10.1145/3508069
Authors
- Publisher:
- Association for Computing Machinery
- Journal:
- ACM Transactions on Computational Logic More from this journal
- Volume:
- 23
- Issue:
- 3
- Article number:
- 14
- Publication date:
- 2022-04-06
- Acceptance date:
- 2021-12-01
- DOI:
- EISSN:
-
1557-945X
- ISSN:
-
1529-3785
- Language:
-
English
- Keywords:
- Pubs id:
-
1226837
- Local pid:
-
pubs:1226837
- Deposit date:
-
2021-12-27
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2022
- Rights statement:
- © 2022 Association for Computing Machinery.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from the Association for Computing Machinery at: https://doi.org/10.1145/3508069
If you are the owner of this record, you can report an update to it here: Report update to this record