NP-hardness conjecture for PCSP(1in3,Cˇ+)\mathrm{PCSP}(\mathbf{1in3},\mathbf{\check{C}^+})

Let 1in3\mathbf{1in3} and Cˇ+\mathbf{\check{C}^+} be the finite relational templates used in the paper, with a homomorphism 1in3Cˇ+\mathbf{1in3}\to\mathbf{\check{C}^+}. The associated promise constraint satisfaction problem is PCSP(1in3,Cˇ+)\mathrm{PCSP}(\mathbf{1in3},\mathbf{\check{C}^+}). Cˇ+\mathbf{\check{C}^+} hardness conjecture. PCSP(1in3,Cˇ+)\mathrm{PCSP}(\mathbf{1in3},\mathbf{\check{C}^+}) is NP-hard. The paper presents this as an unresolved four-element case and provides evidence for, but does not establish, the claimed hardness.

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).

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.