NP-hardness conjecture for
NP-hardness conjecture for
Let and be the finite relational templates used in the paper, with a homomorphism . The associated promise constraint satisfaction problem is . hardness conjecture. 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
Sign in to submit a solution.
No solutions have been posted yet.