Complexity of the identity checking problem for finite semigroups

J. Almeida   ; M. V. Volkov   ; S. V. Gol'dberg

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 5-22

Résumé

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.

Bibliographie

[1] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] M. I. Kargapolov, Yu. I. Merzlyakov, Osnovy teorii grupp, Nauka, M., 1972 | MR | Zbl

[3] R. Lindon, P. Shupp, Kombinatornaya teoriya grupp, Mir, M., 1980 | MR

[4] S. V. Plescheva, V. Verteshi, “Slozhnost zadachi proverki tozhdestv v 0-prostoi polugruppe”, Izv. Ural. gos. un-ta, 2006, no. 43, Kompyuternye nauki informatsionnye tekhnologii, Vyp. 1, 72–102

[5] E. P. Simelgor, “Tozhdestva v konechnoi simmetricheskoi polugruppe”, Sovremen. algebra, 1974, no. 1, 174–188 | MR

[6] J. Almeida, S. V. Plescheva, M. V. Volkov, “An application of group generic implicit operators to the complexity of identity checking in finite semigroups”, Mezhdunar. algebraich. konf., posvyaschennaya stoletiyu so dnya rozhdeniya P. G. Kontorovicha i 70-letiyu L. N. Shevrina, Tez. dokl., Izd-vo Ural. un-ta, Ekaterinburg, 2005, 16–17

[7] J. Almeida, M. V. Volkov, “Subword complexity of profinite words and subgroups of free profinite semigroups”, Int. J. Algebra and Computation, 16:2 (2006), 221–258 | DOI | MR | Zbl

[8] C. Bergman, G. Slutzki, “Complexity of some problems concerning varieties and quasi-varieties of algebras”, SIAM J. Comput., 30:2 (2000), 359–382 | DOI | MR | Zbl

[9] S. Burris, J. Lawrence, “The equivalence problem for finite rings”, J. Symbolic Computation, 15:1 (1993), 67–71 | DOI | MR | Zbl

[10] S. Burris, J. Lawrence, “Results on the equivalence problem for finite groups”, Algebra Universalis, 52:4 (2005), 495–500 | DOI | MR

[11] C. C. Edmunds, “On certain finitely based varieties of semigroups”, Semigroup Forum, 15:1 (1977), 21–39 | DOI | MR | Zbl

[12] G. Horváth, J. Lawrence, L. Mérai, Cs. Szabó, “The complexity of the equivalence problem for nonsolvable groups”, Bull. London Math. Soc., 39:3 (2007), 433–438 | DOI | MR | Zbl

[13] G. Horváth, Cs. Szabó, “The complexity of checking identities over finite groups”, Int. J. Algebra and Computation, 16:5 (2006), 931–939 | DOI | MR | Zbl

[14] H. B. Hunt III, R. E. Stearns, “The complexity of equivalence for commutative rings”, J. Symbolic Computation, 10:5 (1990), 411–436 | DOI | MR | Zbl

[15] M. Jackson, R. McKenzie, “Interpreting graph colorability in finite semigroups”, Int. J. Algebra and Computation, 16:1 (2006), 119–140 | DOI | MR | Zbl

[16] J. Kalicki, “On comparison of finite algebras”, Proc. Amer. Math. Soc., 3:1 (1952), 36–40 | DOI | MR | Zbl

[17] O. G. Kharlampovich, M. V. Sapir, “Algorithmic problems in varieties”, Int. J. Algebra and Computation, 5:4–5 (1995), 379–602 | DOI | MR | Zbl

[18] A. Kisielewicz, “Complexity of semigroup identity checking”, Int. J. Algebra and Computation, 14:4 (2004), 455–464 | DOI | MR | Zbl

[19] O. Klíma, “Complexity issues of checking identities in finite monoids”, Semigroup Forum (to appear) | MR

[20] M. Kozik, On Some Complexity Problems in Finite Algebras, PhD Dissertation, Vanderbilt University, Nashville, 2004 | MR

[21] M. Kozik, “Computationally and algebraically complex finite algebra membership problems”, Int. J. Algebra and Computation, 17:8 (2007), 1635–1666 | DOI | MR | Zbl

[22] M. Kozik, “Varietal membership problem is 2-EXPTIME complete” (to appear)

[23] C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading–Menlo Park–New York, 1994 | MR | Zbl

[24] J.-E. Pin, Varieties of Formal Languages, North Oxford Academic, Oxford; Plenum, New York, 1986 | MR

[25] S. Seif, “The Perkins semigroup has co-NP-complete term-equivalence problem”, Int. J. Algebra and Computation, 15:2 (2005), 317–326 | DOI | MR | Zbl

[26] S. Seif, Cs. Szabó, “Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields”, Semigroup Forum, 72:2 (2006), 207–222 | DOI | MR | Zbl

[27] Cs. Szabó, V. Vértesi, “The complexity of the word-problem for finite matrix rings”, Proc. Amer. Math. Soc., 132:12 (2004), 3689–3695 | DOI | MR | Zbl

[28] Cs. Szabó, V. Vértesi, “The complexity of checking identities for finite matrix rings”, Algebra Universalis, 51:4 (2004), 439–445 | DOI | MR | Zbl

[29] Cs. Szabó, V. Vértesi, “The identity checking problem in finite rings” (to appear)

[30] Z. Székely, “Computational complexity of the finite algebra membership problem for varieties”, Int. J. Algebra and Computation, 12:6 (2002), 811–823 | DOI | MR | Zbl

[31] P. Tesson, Computational Complexity Questions Related to Finite Monoids and Semigroups, PhD Thesis, McGill University, Montréal, 2003