Polynomial time check for Maltsev polymorphisms in finite structures

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

Computational Complexity

Summary

This paper tackles the question of whether certain mathematical structures, called finite relational structures, have a special kind of operation known as a Maltsev polymorphism. The authors show there is an efficient algorithm that can determine this quickly, even for large structures. Their approach works by transforming the problem to a simpler one involving only pairs of elements, using a property called rectangularity. This result means checking for these polymorphisms is easier than previously thought.

What this means in practice

  • For constraint programmers: Decide effectively if their problem’s underlying structure admits Maltsev polymorphisms that enable faster algorithms for solving constraints.
  • For database system designers: Identify query languages based on structures admitting Maltsev polymorphisms to optimize query evaluation strategies.

A theory result. No direct application yet.

Authors

Dejan Delic, Ali Syed

Abstract

In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.