Larose–Tesson characterization conjecture for logspace CSPs
Let be a finite relational structure that is a core, and let denote the problem of deciding whether an input structure admits a homomorphism to . Let the algebra of polymorphisms of have the indicated congruence properties. Larose–Tesson's CSP complexity characterization conjecture. The following equivalences should hold: (i) is solvable in nondeterministic logspace if and only if the algebra of polymorphisms of is congruence join-semidistributive; (ii) is solvable in logspace if and only if that algebra is congruence join-semidistributive and congruence -permutable for some . 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
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.