- UHRA Home
- Browsing by Author
Browsing by Author "Madelaine, Florent"
Now showing items 1-2 of 2
-
The complexity of quantified constraints: Collapsibility, switchability and the algebraic formulation
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby; Zhuk, Dmitriy (2023-01-18)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 B is a constraint language invariant under ... -
From complexity to algebra and back: : digraph classes, collapsibility and the PGP
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby (Institute of Electrical and Electronics Engineers (IEEE), 2015-08-03)Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, ...