← 研踪 PaperTrailarXiv:2611.14379 · v1
Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures
首次提交 2026-11-11 01:33
版本更新 2026-11-11 01:33
雷达观测 2026-11-11 13:07
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 01:33 · 最新观测版本
Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures
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.
查看此版本解读 →查看此版本原文 ↗