Journal article icon

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:
Publisher copy:
10.1145/3508069

Authors


Expand authors...
Publisher:
Association for Computing Machinery Publisher's website
Journal:
ACM Transactions on Computational Logic Journal website
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


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP