Local consistency as a reduction between constraint satisfaction problems
arxiv(2023)
摘要
We study the use of local consistency methods as reductions between
constraint satisfaction problems (CSPs), and promise version thereof, with the
aim to classify these reductions in a similar way as the algebraic approach
classifies gadget reductions between CSPs. This research is motivated by the
requirement of more expressive reductions in the scope of promise CSPs. While
gadget reductions are enough to provide all necessary hardness in the scope of
(finite domain) non-promise CSP, in promise CSPs a wider class of reductions
needs to be used.
We provide a general framework of reductions, which we call consistency
reductions, that covers most (if not all) reductions recently used for proving
NP-hardness of promise CSPs. We prove some basic properties of these
reductions, and provide the first steps towards understanding the power of
consistency reductions by characterizing a fragment associated to
arc-consistency in terms of polymorphisms of the template. In addition to
showing hardness, consistency reductions can also be used to provide feasible
algorithms by reducing to a fixed tractable (promise) CSP, for example, to
solving systems of affine equations. In this direction, among other results, we
describe the well-known Sherali-Adams hierarchy for CSP in terms of a
consistency reduction to linear programming.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要