一句话：系统研究含关系与运算的有限结构上 CSP 的计算复杂度，给出代数条件并完成二元素结构分类
本文开创性地系统研究有限结构（可同时含关系与运算）上约束满足问题（CSP）的计算复杂度。作者揭示该复杂度问题与一个自然代数问题之间的紧密联系：哪些有限代数只允许多项式多个到其上的同态？他们给出有限代数具备该性质的若干充分条件与必要条件，并证明每个有限方程非平凡代数都具备此性质。作为直接推论，文章得到二元素结构上 CSP 的完整复杂度分类，从而将 Schaefer 对二元素关系结构的分类推广到允许运算的情形。文章还构造二元素结构例子，其有界宽度但不具备关系宽度 (2,3)，说明从描述复杂度角度看，引入运算会带来更丰富的理论。
We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebraic question: which finite algebras admit only polynomially many homomorphisms into them?We give some sufficient and some necessary conditions for a finite algebra to have this property. In particular, we show that every finite equationally nontrivial algebra has this property which gives us, as a simple consequence, a complete complexity classification of CSPs over two-element structures, thus extending the classification for two-element relational structures by Schaefer (STOC'78).We also present examples of two-element structures that have bounded width but do not have relational width (2,3), thus demonstrating that, from a descriptive complexity perspective, allowing operations leads to a richer theory.