Document Open Access Logo

On the Complexity of the Cayley Semigroup Membership Problem

Author Lukas Fleischer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.25.pdf
  • Filesize: 486 kB
  • 12 pages

Document Identifiers

Author Details

Lukas Fleischer
  • FMI, University of Stuttgart , Universitätsstraße 38, 70569 Stuttgart, Germany

Funding

  • Fleischer, Lukas: This work was supported by the DFG grant DI 435/5--2.

Cite AsGet BibTex

Lukas Fleischer. On the Complexity of the Cayley Semigroup Membership Problem. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.25

Abstract

We investigate the complexity of deciding, given a multiplication table representing a semigroup S, a subset X of S and an element t of S, whether t can be expressed as a product of elements of X. It is well-known that this problem is {NL}-complete and that the more general Cayley groupoid membership problem, where the multiplication table is not required to be associative, is {P}-complete. For groups, the problem can be solved in deterministic log-space which raised the question of determining the exact complexity of this variant. Barrington, Kadau, Lange and McKenzie showed that for Abelian groups and for certain solvable groups, the problem is contained in the complexity class {FOLL} and they concluded that these variants are not hard for any complexity class containing {Parity}. The more general case of arbitrary groups remained open. In this work, we show that for both groups and for commutative semigroups, the problem is solvable in {qAC}^0 (quasi-polynomial size circuits of constant depth with unbounded fan-in) and conclude that these variants are also not hard for any class containing {Parity}. Moreover, we prove that {NL}-completeness already holds for the classes of 0-simple semigroups and nilpotent semigroups. Together with our results on groups and commutative semigroups, we prove the existence of a natural class of finite semigroups which generates a variety of finite semigroups with {NL}-complete Cayley semigroup membership, while the Cayley semigroup membership problem for the class itself is not {NL}-hard. We also discuss applications of our technique to {FOLL}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Circuit complexity
Keywords
  • subsemigroup
  • multiplication table
  • generators
  • completeness
  • quasi-polynomial-size circuits
  • FOLL

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jorge Almeida. Some pseudovariety joins involving the pseudovariety of finite groups. Semigroup Forum, 37(1):53-57, Dec 1988. URL: http://dx.doi.org/10.1007/BF02573123.
  2. László Babai. Trading group theory for randomness. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421-429. ACM, 1985. URL: http://dx.doi.org/10.1145/22145.22192.
  3. László Babai. Local expansion of vertex-transitive graphs and random generation in finite groups. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 164-174. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103440.
  4. László Babai, Robert Beals, Jin-Yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '96, pages 498-507, Philadelphia, PA, USA, 1996. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313852.314109.
  5. László Babai, Eugene M. Luks, and Ákos Seress. Permutation groups in NC. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 409-420. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28439.
  6. László Babai, Eugene M. Luks, and Ákos Seress. Permutation groups in NC. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 409-420. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28439.
  7. László Babai and Endre Szemerédi. On the complexity of matrix group problems I. In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984, pages 229-240. IEEE Computer Society, 1984. URL: http://dx.doi.org/10.1109/SFCS.1984.715919.
  8. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in nc¹. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 1-5. ACM, 1986. URL: http://dx.doi.org/10.1145/12130.12131.
  9. David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, and Pierre McKenzie. On the complexity of some problems on groups input as multiplication tables. J. Comput. Syst. Sci., 63(2):186-200, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1764.
  10. David A. Mix Barrington and Pierre McKenzie. Oracle branching programs and logspace versus P. Inf. Comput., 95(1):96-115, 1991. URL: http://dx.doi.org/10.1016/0890-5401(91)90017-V.
  11. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC¹. J. ACM, 35:941-952, 1988. Google Scholar
  12. Martin Beaudry. Membership testing in commutative transformation semigroups. Inf. Comput., 79(1):84-93, 1988. URL: http://dx.doi.org/10.1016/0890-5401(88)90018-1.
  13. Martin Beaudry. Membership Testing in Transformation Monoids. PhD thesis, McGill University, Montreal, Quebec, 1988. Google Scholar
  14. Martin Beaudry. Membership testing in threshold one transformation monoids. Inf. Comput., 113(1):1-25, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1062.
  15. Martin Beaudry, Pierre McKenzie, and Denis Thérien. The membership problem in aperiodic transformation monoids. J. ACM, 39(3):599-616, 1992. URL: http://dx.doi.org/10.1145/146637.146661.
  16. Ravi B. Boppana. The average sensitivity of bounded-depth circuits. Inf. Process. Lett., 63(5):257-261, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00131-2.
  17. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan. Near-optimal small-depth lower bounds for small distance connectivity. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 612-625. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897534.
  18. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 36-41. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.34.
  19. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20. ACM, 1986. URL: http://dx.doi.org/10.1145/12130.12132.
  20. Neil D. Jones and William T. Laaser. Complete problems for deterministic polynomial time. Theor. Comput. Sci., 3(1):105-117, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90068-2.
  21. Neil D. Jones, Y. Edmund Lien, and William T. Laaser. New problems complete for nondeterministic loc space. Mathematical Systems Theory, 10:1-17, 1976. URL: http://dx.doi.org/10.1007/BF01683259.
  22. P. Levi. Über die Untergruppen der freien Gruppen. (2. Mitteilung). Mathematische Zeitschrift, 37:90-97, 1933. URL: http://eudml.org/doc/168437.
  23. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  24. Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 1-10. IEEE Computer Society, 1985. URL: http://dx.doi.org/10.1109/SFCS.1985.49.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact