Сложность проверки тождеств в полугруппах преобразований ранга 2

Abstract

Мы исследуем полугруппы T2(n), состоящие из всех преобразований n-элементного множества с не более чем 2-элементным образом, и показываем, что задача проверки тождеств в полугруппе T2(n) разрешима за полиномиальное время при n ≠ 3 и co-NP-complete при n = 3.

We study the semigroups T2(n) consisting of all transformations of an n-element set with at most 2-element range. We show that the identity checking problem for T2(n) is solvable in polynomial time whenever n ≠ 3 and is co-NP-complete for n = 3.