5 papers
Sensitive instances of the Constraint Satisfaction Problem
Libor Barto, Marcin Kozik, Johnson Tan +1
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instanc…
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…
Accessible set endofunctors are universal
Libor Barto
It is shown that every concretizable category can be fully embedded into the category of accessible set functors and natural transformations.
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…
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
Libor Barto, Michael Pinsker
We prove that an -categorical core structure primitively positively interprets all finite structures with parameters if and only if some stabilizer of its polymorphism clone has…