一句话：将数据库 UCQ 的 resilience 问题归约为无限域 VCSP，给出硬度与多项式可解条件，并对无环情形得到复杂度二分。
本文研究值约束满足问题（VCSP）在可数无限域上的复杂度，其中代价函数的自同构群构成寡态置换群。作者给出了一个硬度条件，它推广了经典 CSP 中的 pp-可构造性，并给出基于分数多态（fractional polymorphisms）的多项式时间可解性条件。随后，作者观察到数据库理论中袋语义下合取查询并（UCQ）的 resilience 问题可视为这类 VCSP 的特例。由此，他们对关联无环（incidence-acyclic）UCQ 得到复杂度二分，并用该方法确定了一个此前未决查询的复杂度，最后猜想其硬度与可解性条件对 UCQ resilience 问题相匹配。
Valued constraint satisfaction problems (VCSPs) constitute a large class of computational optimisation problems. It was shown recently that, over finite domains, every VCSP is in P or NP-complete, depending on the admitted cost functions. In this article, we study cost functions over countably infinite domains whose automorphisms form an oligomorphic permutation group. Our results include a hardness condition based on a generalisation of pp-constructability as known from classical CSPs and a polynomial-time tractability condition based on the concept of fractional polymorphisms. We then observe that the resilience problem for unions of conjunctive queries (UCQs) studied in database theory, under bag semantics, may be viewed as a special case of the VCSPs that we consider. We obtain a complexity dichotomy for the case of incidence-acyclic UCQs and exemplarily use our methods to determine the complexity of a query that had remained open in the literature. Further, we conjecture that our hardness and tractability conditions match for resilience problems for UCQs.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{BodirskySL26,
title = {The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems},
author = {Manuel Bodirsky and Žaneta Semanišinová and Carsten Lutz},
booktitle = {LICS},
year = {2024},
doi = {10.1145/3661814.3662071}
}