6 citations · 20 across the 15 of their papers we have counts for
20 papers
Submaximal clones over a three-element set up to minor-equivalence
Albert Vucaj, Dmitriy Zhuk
We study clones modulo minor homomorphisms, which are mappings from one clone to another preserving arities of operations and respecting permutation and identification of variables…
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…