Larose–Tesson characterization conjecture for logspace CSPs

At least 11 years old · documented by

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.

References

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.