The VCSP tractability dichotomy conjecture for resilience templates
Statement
Let be a union of connected conjunctive queries over a signature , let be the associated valued structure, and let be a finitely bounded homogeneous expansion of . Let denote the Boolean valued structure used in the pp-construction condition. VCSP tractability dichotomy conjecture. Exactly one of the following holds: has a pp-construction in , and is NP-complete; or has a fractional polymorphism of some arity that is canonical and pseudo cyclic with respect to , and is in P. This adapts the conjecture cited from the VCSP literature to the valued structures used here; the first condition is known to imply NP-hardness, while the proposed converse and the asserted dichotomy remain 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.