NP-hardness conjecture for promise CSPs between and
For integers , let and denote the corresponding symmetric relational templates, and let be the promise problem whose instances homomorphically map to and whose outputs must homomorphically map to . -template hardness conjecture. For every , is NP-hard. The paper has classified the relevant three-element cases except for ; the smallest case 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.