Publication:4407431
From MaRDI portal
zbMath1032.20037MaRDI QIDQ4407431
Andrei A. Bulatov, Mikhail V. Volkov, Peter G. Jeavons
Publication date: 4 January 2004
NP-complete problems; finite semigroups; constraint satisfaction problem; block groups; tractable problems
68Q25: Analysis of algorithms and problem complexity
20M05: Free semigroups, generators and relations, word problems
Related Items
Block-Groups and Hall Relations, Quantified Constraints in Twenty Seventeen, THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM, Recent Results on the Algebraic Approach to the CSP, A new tractable class of constraint satisfaction problems, Combinatorial problems raised from 2-semilattices