14 citations · 24 across the 10 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2021
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…
cs.CC2015★ 2 cited
From complexity to algebra and back: digraph classes, collapsibility and the PGP
Catarina Carvalho, Florent Madelaine, Barnaby Martin
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…