Сложность задачи проверки тождеств в одной конечной 0-простой полугруппе

Abstract

Под задачей проверки тождеств ID-CHECK (A) в конечной алгебре A понимается комбинаторная задача распознавания, принимающая на вход пару терминов p=q и отвечающая на вопрос, выполнено ли тождество p=g в алгебре A. В работе исследуется вычислительная сложность задачи ID-CHECK в одной 19-элементной 0-простой полугруппе M. Доказана соNP-полнота задачи ID-CHECK (M), а также показано, что для всех меньших по числу элементов 0-простых полугрупп задача ID-CHECK полиномиальна. Кроме того, в работе исследуются две задачи о гомоморфизмах двудольных графов, для которых доказывается их соNP-полнота и проводится полиномиальная сводимость к ID-CHECK (M).

The identity checking problem ID-CHECK(.A) for a finite algebra .A is a combinatorial decision problem whose instance is a pair of terms p = q and the question is whether or not .A satisfies p = q. We study the computational complexity of checking identities in a 19-element 0-simple semigroup .M. We show that .M is the smallest 0-simple semigroup for which this problem is coNP-complete. We also investigate two problems on homomorphisms of bipartite graphs, prove their coNP-completeness, and reduce them to ID.CHECK(.M).