We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details for Dr Barnaby Martin

Đapić, Petar, Marković, Petar & Martin, Barnaby (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic 18(1): 2.

Author(s) from Durham


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.