6 citations · 20 across the 15 of their papers we have counts for
10 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 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…
Strong subalgebras and the Constraint Satisfaction Problem
Dmitriy Zhuk
In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language is tractable if and only if is preserved by a weak near-unanimity (WNU)…