Deciding the Existence of Quasi Weak Near Unanimity Terms in Finite Algebras

Abstrakt

We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given finite algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations.

Klíčová slova

• Computational complexity
• Maltsev condition
• Taylor term
• weak near unanimity
• local to global