The tractability conjecture for finite domain Constraint Satisfaction Problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction, in some precise technical sense, from the 3-SAT problem; otherwise, they are NP-complete. Its recent resolution draws on an algebraic characterization of the conjectured borderline: the CSP of a finite structure permits no natural reduction from 3-SAT if and only if the stabilizer of the polymorphism clone of the core of the structure satisfies some nontrivial system of identities, and such satisfaction is always witnessed by several specific nontrivial systems of identities which do not depend on the structure. The tractability conjecture has been generalized in the above formulation to a certain class of infinite domain CSPs, namely, CSPs of reducts of finitely bounded homogeneous structures. It was subsequently shown that the conjectured borderline between hardness and tractability, i.e., a natural reduction from 3-SAT, can be characterized for this class by a combination of algebraic and topological properties. However, it was not known whether the topological component is essential in this characterization. We provide a negative answer to this question by proving that the borderline is characterized by one specific algebraic identity, namely the pseudo-Siggers identity $\alpha s(x,y,x,z,y,z) \approx \beta s(y,x,z,x,z,y)$. This accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our main theorem is also of independent mathematical interest, characterizing a topological property of any $\omega$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).
翻译:有限域域限制满意度问题(CSPs) 的缩略图显示,当3SAT问题没有自然减少时,在某种精确的技术意义上,这种 CSPs在多元时间里是可以溶解的;否则,它们是NP;它最近的解析来自对推测边界的代数描述:一个有限结构的 CSP允许3SAT的自然减缩,条件是结构核心的多形态化克隆(多形态化克隆)满足了某种非三角的特性系统,而且这种满意度总是通过若干不取决于结构的特性的特定的非三角系统来见证的。上面的缩略图性共性已经普遍化为某种无限的域 CSPs, 即固定的同质结构的缩影化。后来显示,在结构核心的硬性和可感知性(即从3SAT的自然减缩), 对于这一类而言,一个主要的数值值的内值和顶部的内值性能步骤,这个内值的内值性能性能性能, 也是我们所知道的直系的内值。