In 2017, Bulatov and Zhuk independently proved the Feder-Vardi dichtomy conjecture: every constraint satisfaction problem (CSP) with a finite domain is in P or NP-complete. What remains open is a classifictation of
which finite-domain CSPs are in the complexity classes L, NL, NC, and which are P-complete. These questions are open even if the template structure is an orientation of a tree.

In this talk I will present results about CSPs of orientations of trees that were obtained with the help of computer experiments. We computed the smallest tree that is NL-hard (assuming L is not NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bulin concerning a question of Hell, Nesetril and Zhu, namely that "easy trees lack the ability to count". To obtain these results we make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.

Joint work with Jakub Bulin, Florian Starke, and Michael Wernthaler.