Resilience tractability conjecture for unions of connected conjunctive queries
Statement
Let be a union of connected conjunctive queries over the signature , and let . Write for the associated valued structure. A fractional polymorphism of arity is a probability distribution on -ary operations satisfying the corresponding valued-polymorphism inequalities; it is canonical and pseudo cyclic with respect to when it has the symmetry properties defined in the paper. A pp-construction is the paper's primitive-positive construction operation.
Resilience tractability conjecture. If the structure has no pp-construction in , then has a fractional polymorphism of arity which is canonical and pseudo cyclic with respect to .
In that case, the associated is in . Together with the paper's hardness result, this conjecture would imply a P-versus-NP-complete dichotomy for resilience problems for finite unions of conjunctive queries.
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.