Quantified constraint satisfaction problem on semicomplete digraphs

Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке: https://open.uns.ac.rs/handle/123456789/3302

Назив:	Quantified constraint satisfaction problem on semicomplete digraphs
Аутори:	Đapić, Petar Marković, Petar Martin B.
Датум издавања:	1-апр-2017
Часопис:	ACM Transactions on Computational Logic
Сажетак:	© 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
Налази се у колекцијама:	PMF Publikacije/Publications