nach oben

Theory of Computing Systems

Erschienen in:

12.02.2018

The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC⁰

verfasst von: Alexei Miasnikov, Svetla Vassileva, Armin Weiß

Erschienen in: Theory of Computing Systems | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We show that the conjugacy problem in a wreath product A ≀ B is uniform-TC⁰-Turing-reducible to the conjugacy problem in the factors A and B and the power problem in B. If B is torsion free, the power problem in B can be replaced by the slightly weaker cyclic submonoid membership problem in B. Moreover, if A is abelian, the cyclic subgroup membership problem suffices, which itself is uniform-AC⁰-many-one-reducible to the conjugacy problem in A ≀ B. Furthermore, under certain natural conditions, we give a uniform TC⁰ Turing reduction from the power problem in A ≀ B to the power problems of A and B. Together with our first result, this yields a uniform TC⁰ solution to the conjugacy problem in iterated wreath products of abelian groups – and, by the Magnus embedding, also in free solvable groups.

Vorheriger Artikel Verification of Quantum Computation: An Overview of Existing Approaches

Nächster Artikel On Algorithmic Statistics for Space-bounded Algorithms

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC¹. J. Comput. Syst. Sci. 41(3), 274–306 (1990). https://doi.org/10.1016/0022-0000(90)90022-D CrossRefMATH

Craven, M.J., Jimbo, H.C.: Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography. Groups Complex. Cryptol. 4, 135–165 (2012). https://doi.org/10.1515/gcc-2016-0012 MathSciNetMATH

Dehn, M.: Über unendliche diskontinuierliche Gruppen. Math. Ann. 71(1), 116–144 (1911). https://doi.org/10.1007/BF01456932 MathSciNetCrossRefMATH

Diekert, V., Myasnikov, A. G., Weiß, A.: Conjugacy in baumslag’s group, generic case complexity, and division in power circuits. In: Latin American Theoretical Informatics Symposium, pp 1–12 (2014)

Grigoriev, D., Shpilrain, V.: Authentication from matrix conjugation. Groups Complex. Cryptol. 1, 199–205 (2009)MathSciNetMATH

Gul, F., Sohrabi, M., Ushakov, A.: Magnus embedding and algorithmic properties of groups F/N ^(d). Trans. Amer. Math. Soc. 369(9), 6189–6206 (2017). https://doi.org/10.1090/tran/6880 MathSciNetCrossRefMATH

Hesse, W.: Division is in uniform TC⁰. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001, Proceedings, Lecture Notes in Computer Science, vol. 2076, pp 104–114. Springer (2001)

Hesse, W., Allender, E., Barrington, D. A. M.: Uniform constant-depth threshold circuits for division and iterated multiplication. JCSS 65, 695–716 (2002)MathSciNetMATH

Kargapolov, M. I., Remeslennikov, V. N.: The conjugacy problem for free solvable groups. Algebra i Logika Sem. 5(6), 15–25 (1966)MathSciNetMATH

10.

Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.S., Park, C.: New public-key cryptosystem using braid groups. In: Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Computer Science. https://doi.org/10.1007/3-540-44598-6_10, vol. 1880, pp 166–183. Springer, Berlin (2000)

11.

König, D., Lohrey, M.: Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica (2017). https://doi.org/10.1007/s00453-017-0343-z

12.

Krebs, A., Lange, K., Reifferscheid, S.: Characterizing TC⁰ in terms of infinite groups. Theory Comput. Syst. 40 (4), 303–325 (2007). https://doi.org/10.1007/s00224-006-1310-2 MathSciNetCrossRefMATH

13.

Lange, K., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K., Ibarra, O.H. (eds.) ISAAC 1998, Proceedings, Lecture Notes in Computer Science. https://doi.org/10.1007/3-540-49381-6_27, vol. 1533, pp 247–256. Springer (1998)

14.

Maciel, A., Thérien, D.: Threshold circuits of small majority-depth. Inf. Comput. 146(1), 55–83 (1998). https://doi.org/10.1006/inco.1998.2732 MathSciNetCrossRefMATH

15.

Magnus, W.: On a theorem of Marshall Hall. Ann. of Math. (2) 40, 764–768 (1939)MathSciNetCrossRefMATH

16.

Matthews, J.: The conjugacy problem in wreath products and free metabelian groups. Trans. Amer. Math. Soc. 121, 329–339 (1966)MathSciNetCrossRefMATH

17.

Miller, C.F. III: On group-theoretic decision problems and their classification, Ann. of Math. Studies, vol. 68. Princeton University Press, NJ (1971)

18.

Myasnikov, A., Roman’kov, V., Ushakov, A., Vershik, A.: The word and geodesic problems in free solvable groups. Trans. Amer. Math. Soc. 362(9), 4655–4682 (2010). https://doi.org/10.1090/s0002-9947-10-04959-7 MathSciNetCrossRefMATH

19.

Myasnikov, A., Vassileva, S., Weiß, A.: The conjugacy problem in free solvable groups and wreath products of abelian groups is in T C ⁰. In: CSR 2017. https://doi.org/10.1007/978-3-319-58747-9_20, pp 217–231. Proceedings (2017)

20.

Myasnikov, A., Vassileva, S., Weiss, A.: Log-Space Complexity of the Conjugacy Problem in Wreath Products, chap. 12, pp. 215–236. World Scientific (2017). https://doi.org/10.1142/9789813204058_0012

21.

Myasnikov, A., Weiß, A.: TC⁰ circuits for algorithmic problems in nilpotent groups. ArXiv e-prints (2017)

22.

Remeslennikov, V., Sokolov, V. G.: Certain properties of the Magnus embedding. Algebra i logika 9(5), 566–578 (1970)MathSciNetCrossRef

23.

Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993)

24.

Shpilrain, V., Zapata, G.: Combinatorial group theory and public key cryptography. Appl. Algebra Engrg. Comm. Comput. 17, 291–302 (2006)MathSciNetCrossRefMATH

25.

Vassileva, S.: Polynomial time conjugacy in wreath products and free solvable groups. Groups Complex. Cryptol. 3(1), 105–120 (2011). https://doi.org/10.1515/GCC.2011.005 MathSciNetMATH

26.

Vollmer, H.: Introduction to Circuit Complexity. Springer, Berlin (1999)CrossRefMATH

27.

Waack, S.: The parallel complexity of some constructions in combinatorial group theory, pp 492–498. Springer-Verlag New York, Inc., New York (1990)

28.

Wang, L., Wang, L., Cao, Z., Okamoto, E., Shao, J.: New constructions of public-key encryption schemes from conjugacy search problems. In: Information security and cryptology, Lecture Notes in Comput. Sci. https://doi.org/10.1007/978-3-642-21518-6_1, vol. 6584, pp 1–17. Springer, Heidelberg (2011)

29.

Weiß, A.: A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. In: Algebra and computer science, Contemporary Mathematics, vol. 677, pp 185–212. American Mathematics Society, Providence (2016)

Titel: The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0
verfasst von: Alexei Miasnikov
Svetla Vassileva
Armin Weiß
Publikationsdatum: 12.02.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9849-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2019

Cascade Heap: Towards Time-Optimal Extractions

Generic Results for Concatenation Hierarchies

Foreword

Green’s Relations in Deterministic Finite Automata

On Algorithmic Statistics for Space-bounded Algorithms

The Descriptive Complexity of Subgraph Isomorphism Without Numerics

Premium Partner