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

At least 5 years old · documented by

For integers 2≤k<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 2≤k<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.

References

Primary source

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

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.