NP-hardness conjecture for promise CSPs between LOk\mathbf{LO}_k and LOl\mathbf{LO}_l

From papers

For integers 2k<l2\leq k<l, let LOk\mathbf{LO}_k and LOl\mathbf{LO}_l denote the corresponding symmetric relational templates, and let PCSP(LOk,LOl)\mathrm{PCSP}(\mathbf{LO}_k,\mathbf{LO}_l) be the promise problem whose instances homomorphically map to LOk\mathbf{LO}_k and whose outputs must homomorphically map to LOl\mathbf{LO}_l. LO\mathbf{LO}-template hardness conjecture. For every 2k<l2\leq k<l, PCSP(LOk,LOl)\mathrm{PCSP}(\mathbf{LO}_k,\mathbf{LO}_l) is NP-hard. The paper has classified the relevant three-element cases except for LO3\mathbf{LO}_3; the smallest case PCSP(LO2,LO3)\mathrm{PCSP}(\mathbf{LO}_2,\mathbf{LO}_3) is therefore among the unresolved instances motivating the conjecture.

Progress summary

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

Sources & referencesView supporting material

Primary source

Libor Barto, Diego Battistelli and Kevin M. Berg, “Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case”, arXiv:2010.04623 (2020).

Solutions 0

No solutions have been posted yet.