Larose–Tesson characterization conjecture for logspace CSPs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.