Promise constraint satisfaction problems - Brandts-Longtin, A (2022)
The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists under the strict constraints, the task is to find a solution under the weak constraints.