Document Open Access Logo

TC^0 Circuits for Algorithmic Problems in Nilpotent Groups

Authors Alexei Myasnikov, Armin Weiß

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.23.pdf
  • Filesize: 477 kB
  • 14 pages

Document Identifiers

Author Details

Alexei Myasnikov
Armin Weiß

Cite As Get BibTex

Alexei Myasnikov and Armin Weiß. TC^0 Circuits for Algorithmic Problems in Nilpotent Groups. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.23

Abstract

Recently, Macdonald et. al. showed that many algorithmic problems for finitely generated nilpotent groups including computation of normal forms, the subgroup membership problem, the conjugacy problem, and computation of subgroup presentations can be done in LOGSPACE. Here we follow their approach and show that all these problems are complete for the uniform circuit class TC^0 - uniformly for all r-generated nilpotent groups of class at most c for fixed r and c. 
	
Moreover, if we allow a certain binary representation of the inputs, then the word problem and computation of normal forms is still in uniform TC^0, while all the other problems we examine are shown to be TC^0-Turing reducible to the problem of computing greatest common divisors and expressing them as linear combinations.

Subject Classification

Keywords
  • nilpotent groups
  • TC^0
  • abelian groups
  • word problem
  • conjugacy problem
  • subgroup membership problem
  • greatest common divisors

Metrics

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

References

  1. Norman Blackburn. Conjugacy in nilpotent groups. Proceedings of the American Mathematical Society, 16(1):143-148, 1965. Google Scholar
  2. William W. Boone. The Word Problem. Ann. of Math., 70(2):207-265, 1959. Google Scholar
  3. Max Dehn. Ueber unendliche diskontinuierliche Gruppen. Math. Ann., 71:116-144, 1911. Google Scholar
  4. Bettina Eick and Delaram Kahrobaei. Polycyclic groups: A new platform for cryptology? ArXiv Mathematics e-prints, 2004. URL: http://arxiv.org/abs/math/0411077.
  5. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. Electronic Colloquium on Computational Complexity (ECCC), 18:128, 2011. URL: http://eccc.hpi-web.de/report/2011/128.
  6. Alberd Garreta, Alexei Miasnikov, and Denis Ovchinnikov. Properties of random nilpotent groups. ArXiv e-prints, December 2016. URL: http://arxiv.org/abs/1612.01242.
  7. Philip Hall. The Edmonton notes on nilpotent groups. Queen Mary College Mathematics Notes. Mathematics Department, Queen Mary College, London, 1969. Google Scholar
  8. William Hesse. Division is in uniform TC⁰. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, ICALP, volume 2076 of Lecture Notes in Computer Science, pages 104-114. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-48224-5_9.
  9. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65:695-716, 2002. Google Scholar
  10. Mikhail I. Kargapolov and Ju. I. Merzljakov. Fundamentals of the theory of groups, volume 62 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1979. Translated from the second Russian edition by Robert G. Burns. Google Scholar
  11. Mikhail I. Kargapolov, Vladimir. N. Remeslennikov, N. S. Romanovskii, Vitaly A. Roman'kov, and V. A. Čurkin. Algorithmic questions for σ-powered groups. Algebra i Logika, 8:643-659, 1969. Google Scholar
  12. Daniel König and Markus Lohrey. Evaluating matrix circuits. In Computing and combinatorics, volume 9198 of Lecture Notes in Comput. Sci., pages 235-248. Springer, Cham, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21398-9_19.
  13. Klaus-Jörn Lange and Pierre McKenzie. On the complexity of free monoid morphisms. In Kyung-Yong Chwa and Oscar H. Ibarra, editors, Algorithms and Computation, 9th International Symposium, ISAAC'98, Taejon, Korea, December 14-16, 1998, Proceedings, volume 1533 of Lecture Notes in Computer Science, pages 247-256. Springer, 1998. URL: http://dx.doi.org/10.1007/3-540-49381-6_27.
  14. Charles. R. Leedham-Green and Leonard H. Soicher. Symbolic collection using Deep Thought. LMS J. Comput. Math., 1:9-24 (electronic), 1998. URL: http://dx.doi.org/10.1112/S1461157000000127.
  15. Richard J. Lipton and Yechezkel Zalcstein. Word problems solvable in logspace. J. ACM, 24(3):522-526, July 1977. URL: http://dx.doi.org/10.1145/322017.322031.
  16. Jeremy MacDonald, Alexei G. Myasnikov, Andrey Nikolaev, and Svetla Vassileva. Logspace and compressed-word computations in nilpotent groups. CoRR, abs/1503.03888, 2015. URL: http://arxiv.org/abs/1503.03888.
  17. Anatoly I. Mal'cev. On homomorphisms onto finite groups. Transl., Ser. 2, Am. Math. Soc., 119:67-79, 1983. Translation from Uch. Zap. Ivanov. Gos. Pedagog Inst. 18, 49-60 (1958). Google Scholar
  18. Andrzej Mostowski. Computational algorithms for deciding some problems for nilpotent groups. Fundamenta Mathematicae, 59(2):137-152, 1966. URL: http://eudml.org/doc/213887.
  19. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. The Post correspondence problem in groups. J. Group Theory, 17(6):991-1008, 2014. URL: http://dx.doi.org/10.1515/jgth-2014-0022.
  20. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Non-commutative lattice problems. J. Group Theory, 19(3):455-475, 2016. URL: http://dx.doi.org/10.1515/jgth-2016-0506.
  21. Alexei G. Myasnikov and Armin Weiß. TC^0 circuits for algorithmic problems in nilpotent groups. CoRR, abs/1702.06616, 2017. URL: http://arxiv.org/abs/1702.06616.
  22. Pyotr S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, pages 1-143, 1955. In Russian. Google Scholar
  23. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993. Google Scholar
  24. Charles C. Sims. Computation with finitely presented groups, volume 48 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1994. URL: http://dx.doi.org/10.1017/CBO9780511574702.
  25. Heribert Vollmer. Introduction to Circuit Complexity. Springer, Berlin, 1999. Google Scholar
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 About DROPS Imprint Privacy Contact