判定有限关系结构的Maltsev多态性存在性的复杂性
Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures
Dejan Delic, Ali Syed
AI 速读 基于摘要
作者报告判定有限关系结构是否具有Maltsev多态性可在多项式时间内完成,并借助二元关系矩形性给出归约证明。
cs.CC
查看原文摘要
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.