NP-hardness conjecture for promise CSPs between LO_k and LO_l
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.