This is joint work with Libor Barto and Ross Willard.

We generalize the result of Dalmau and Krokhin and prove that a finite template with compatible near-unanimity polymorphisms (or equivalently, by Barto’s result, J´onsson polymorphisms) generates a CSP with a complement solvable by a program of linear Datalog. This places the CSP in NL.