The tractable-or-NP-hard dichotomy conjecture for generic combinations
Statement
Let and be countably infinite -categorical structures without algebraicity, not preserved by all permutations, and with the cross prevention property. A binary injective polymorphism is a binary operation preserving all relations of a structure and injective as a function; a constant polymorphism is a constant operation preserving all relations. The constraint satisfaction problem of a structure is denoted by , and denotes its theory.
Tractable-or-NP-hard dichotomy conjecture. If either
- is in P and has a binary injective polymorphism for both and , or
- has a constant polymorphism for both and ,
then
is in P. Otherwise,
is NP-hard.
The conjecture would extend the paper's tractability and hardness results to combinations of broad classes of countably infinite -categorical structures with cross prevention. It remains open in general.
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.