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

Доказывается co-NP-полнота задачи проверки тождеств в конечной полугруппе $S$ при условии, что $S$ имеет неразрешимую подгруппу или является полугруппой всех преобразований 3-элементного множества. Библ. – 31 назв.