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 similar way as the algebraic approach classifies gadget reductions between CSPs. We classify a use of arc-consistency in this way, provide first steps into classification of general $k$-consistency, and ask whether every tractable finite template CSP is reducible by such a reduction to solving systems of affine Diophantine equations.
翻译:我们研究地方一致性方法的使用,作为限制满意度问题(CSPs)及其前景版本之间的减少,目的是将这些减少与代数法方法将CSPs之间的减少分类相类似,以便将这些减少分类。 我们用这种方式对使用“三重一致性”进行分类,为一般美元一致性分类提供初步步骤,并询问每个可移植的有限模板CSP是否都可以通过这种减少来降低,从而解决近亲式等式系统。