ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let μ\mu be a union of connected conjunctive queries over the signature τ\tau, and let σ⊆τ\sigma\subseteq\tau. Write Γ:=Γμ,σ\Gamma:=\Gamma_{\mu,\sigma} for the associated valued structure. A fractional polymorphism of arity ℓ\ell is a probability distribution on ℓ\ell-ary operations satisfying the corresponding valued-polymorphism inequalities; it is canonical and pseudo cyclic with respect to Aut⁡(Γ)\operatorname{Aut}(\Gamma) 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 ({0,1};OIT⁡)(\{0,1\};\operatorname{OIT}) has no pp-construction in Γ\Gamma, then Γ\Gamma has a fractional polymorphism of arity ℓ≥2\ell\geq2 which is canonical and pseudo cyclic with respect to Aut⁡(Γ)\operatorname{Aut}(\Gamma).

In that case, the associated VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) is in P⁡\operatorname{P}. 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.