Larose–Tesson characterization conjecture for logspace CSPs

Let A\mathbb{A} be a finite relational structure that is a core, and let CSP(A)\operatorname{CSP}(\mathbb{A}) denote the problem of deciding whether an input structure admits a homomorphism to A\mathbb{A}. Let the algebra of polymorphisms of A\mathbb{A} have the indicated congruence properties. Larose–Tesson's CSP complexity characterization conjecture. The following equivalences should hold: (i) CSP(A)\operatorname{CSP}(\mathbb{A}) is solvable in nondeterministic logspace if and only if the algebra of polymorphisms of A\mathbb{A} is congruence join-semidistributive; (ii) CSP(A)\operatorname{CSP}(\mathbb{A}) is solvable in logspace if and only if that algebra is congruence join-semidistributive and congruence nn-permutable for some nn. These conjectures seek algebraic characterizations of the CSPs in NL and L; the source says that the hardness directions had been proved and presents the displayed formulation as widely discussed.

Sources & referencesView supporting material

Primary source

Jakub Bulín, Dejan Delic, Marcel Jackson and Todd Niven, “A finer reduction of constraint problems to digraphs”, arXiv:1406.6413 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.