4 papers · 1 filter
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…
Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)
Libor Barto, Michael Pinsker
The tractability conjecture for finite domain Constraint Satisfaction Problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction,…