J. Almeida, M. V. Volkov, S. V. Gol'dberg, “Complexity of the identity checking problem for finite semigroups”, Zap. Nauchn. Sem. POMI, 2008, Volume 358,Pages <nobr>5

This article is cited in 14 papers

Complexity of the identity checking problem for finite semigroups

J. Almeida^a, M. V. Volkov^b, S. V. Gol'dberg^b

^a University of Porto
^b Ural State University

Abstract: We prove that the identity checking problem in a finite semigroup $S$ is co-NP-complete whenever $S$ has a nonsolvable subgroup or $S$ is the semigroup of all transformations on a 3-element set. Bibl. – 31 titles.

UDC: 512.552

Received: 04.06.2007