6 citations · 20 across the 15 of their papers we have counts for
6 papers · 1 filter
The complexity of the Quantified CSP having the polynomially generated powers property
Dmitriy Zhuk
It is known that if an algebra of polymorphisms of the constraint language has the Polynomially Generated Powers (PGP) Property then the Quantified CSP can be reduced to the CSP ov…
Small Promise CSPs that reduce to large CSPs
Alexandr Kazda, Peter Mayr, Dmitriy Zhuk
For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does n…
The lattice of clones of self-dual operations collapsed
Manuel Bodirsky, Albert Vucaj, Dmitriy Zhuk
There are continuum many clones on a three-element set even if they are considered up to \emph{homomorphic equivalence}. The clones we use to prove this fact are clones consisting…
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Catarina Carvalho, Florent Madelaine, Barnaby Martin +1
Let A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, we argue that if A satisfies the polynomially generated powers property (PGP) and…
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
Libor Barto, Zarathustra Brady, Andrei Bulatov +2
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend p…
The complete classification for quantified equality constraints
Dmitriy Zhuk, Barnaby Martin, Michal Wrona
We prove that QCSP is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP…