Behrisch, M. (2024, February 10). Reduced weak base relations for maximal clones on finite sets [Conference Presentation]. AAA104 - 104th Workshop on General Algebra, Blagoevgrad, Bulgaria. https://doi.org/10.34726/8341
Weak bases of relational clones have been used in the past as a background tool to obtain more fine-grained complexity classifications of computational problems, for example, when certain types of reductions are not allowable for theoretical reasons or are not available for practical reasons. Singleton weakbase relations for all Boolean relational clones were determined by Lagerkvist and by the speaker. Beyond the two-element case not much has been known for a while. Recently, in work of Romov on associated intervals, criteria for singularity of clones on finite sets (with possibly more than two elements) have been given, and it can be shown that for a finitely related relational clone with a singular polymorphism clone, every finite generating set of the relational clone is a weak base. In this talk we present reduced weak base relations (forming singleton weak bases) for all maximal clones on finite at least three-element sets. In some cases the familiar relations from Rosenberg’s classification of maximal clones can be re-used as weak base relations, in certain others they provably cannot.