7 papers
Decidability of Interpretability
Roman Feller, Michael Pinsker
The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of Constraint Satisfaction Problems (CSPs) of first-order reducts of finitely…
When Darwin met Ianus: dichotomies of expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (…
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.
New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
Tomáš Nagy, Michael Pinsker, Michał Wrona
The path to the solution of Feder-Vardi dichotomy conjecture by Bulatov and Zhuk led through showing that more and more general algebraic conditions imply polynomial-time algorithm…
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative template…
An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
Roman Feller, Michael Pinsker
For a set F of finite tournaments, the F-free orientation problem is the problem of deciding if a given finite undirected graph can be oriented in such a way that the resulting ori…
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…