4 papers · 1 filter
Combinatorial Gap Theorem and Reductions between Promise CSPs
Libor Barto, Marcin Kozik
A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show…
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…
Promises Make Finite (Constraint Satisfaction) Problems Infinitary
Libor Barto
The fixed template Promise Constraint Satisfaction Problem (PCSP) is a recently proposed significant generalization of the fixed template CSP, which includes approximation variants…
Algebraic Theory of Promise Constraint Satisfaction Problems, First Steps
Libor Barto
What makes a computational problem easy (e.g., in P, that is, solvable in polynomial time) or hard (e.g., NP-hard)? This fundamental question now has a satisfactory answer for a qu…