Tue, 19 Nov 2024, 1:25 pm MT
An algebra is called minimal Taylor if its clone satisfies a non-trivial minor condition, but no proper subclone does so. Recently, Barto, Brady, Bulatov, Kozik and Zhuk initiated the systematic study of minimal Taylor algebras, intending to build a unified theory to understand the complexity of constraint satisfaction problems. They conjecture that every minimal Taylor algebra is finitely related, which we disprove by giving a counterexample.
This result can be interpreted as follows: there is an infinite sequence of tractable finite domain CSPs, such that every CSP harder than all problems in the sequence, is already NP-complete.
[video]