2 papers
cs.CC2020
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
Libor Barto, Diego Battistelli, Kevin M. Berg
The Promise Constraint Satisfaction Problem (PCSP) is a recently introduced vast generalization of the Constraint Satisfaction Problem (CSP). We investigate the computational compl…
math.LO2019
The Complexity of Homomorphism Factorization
Kevin M. Berg
We investigate the computational complexity of the problem of deciding if an algebra homomorphism can be factored through an intermediate algebra. Specifically, we fix an algebraic…