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…