Library

Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)

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, in some precise t...

MathematicsComputer Science
Source

Paper

Similar papers

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)M. Bodirsky, A. Mottet, M. Olsák et al.2019 · Logic in Computer Science · 8 citations In Library
Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems)M. Bodirsky, A. Mottet, M. Olsák et al.2019 · arXiv.org · 10 citations In Library
Constraint satisfaction tractability from semi-lattice operations on infinite setsM. Bodirsky, D. Macpherson, Johan Thapper2011 · TOCL · 9 citations In Library
Complexity Classification in Infinite-Domain Constraint SatisfactionM. Bodirsky2012 · arXiv.org · 100 citations In Library
Complexity of Infinite-Domain Constraint SatisfactionM. Bodirsky2021 · 101 citations In Library
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction ProblemsL. Barto, M. Pinsker2016 · Logic in Computer Science · 89 citations In Library
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hardLeonid Dorochko, Michal Wrona2026 · arXiv.org · 0 citations In Library
The Dichotomy for Conservative Constraint Satisfaction is Polynomially DecidableClément Carbonnel2016 · International Conference on Principles and Practice of Constraint Programming · 8 citations In Library
Three Fundamental Questions in Modern Infinite-Domain Constraint SatisfactionMichael Pinsker, Jakub Rydval, Moritz Schobi et al.2025 · 1 citation In Library
Constraint Satisfaction Problem Dichotomy for Finite Templates: a Proof Via Consistency ChecksD. Delic2017 · arXiv: Computational Complexity · 1 citation In Library
© 2026 NYSGPT2525 LLC