Discrete Homotopy and Promise Constraint Satisfaction Problem

Arash Beikmohammadi, Andrei A. Bulatov

The Promise Constraint Satisfaction Problem (PCSP for short) is a generalization of the well-studied Constraint Satisfaction Problem (CSP). The PCSP has its roots in such classic p…