NP-hardness conjecture for promise CSPs between and
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.
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
Sign in to submit a solution.
No solutions have been posted yet.