Back to Search
Start Over
QCSP on Reflexive Tournaments
- Source :
- ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022)
- Publication Year :
- 2021
-
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 H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j 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.<br />Comment: arXiv admin note: text overlap with arXiv:1709.09486
- Subjects :
- Computer Science - Computational Complexity
Subjects
Details
- Database :
- arXiv
- Journal :
- ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022)
- Publication Type :
- Report
- Accession number :
- edsarx.2104.10570
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1145/3508069