Complexity of Spherical Equations in Finite Groups

Caroline Mattes, Alexander Ushakov, Armin Weiß

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

In this paper we investigate computational properties of the Diophantine problem for spherical equations in some classes of finite groups G. We classify the complexity of different variations of the problem, e.g., when G is fixed and when G is a part of the input. When the group G is constant or given as multiplication table, we show that the problem can always be solved in polynomial time. On the other hand, for the permutation groups Sn (with n part of the input), the problem is NP-complete. The situation for matrix groups is quite involved: while we exhibit sequences of 2-by-2 matrices where the problem is NP-complete, in the full group GL(2,p) (p prime and part of the input) it can be solved in polynomial time. We also find a similar behaviour with subgroups of matrices of arbitrary dimension over a constant ring.

Original languageEnglish
Title of host publicationSOFSEM 2024
Subtitle of host publicationTheory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings
EditorsHenning Fernau, Serge Gaspers, Ralf Klasing
Pages383-397
Number of pages15
DOIs
StatePublished - 2024
Event49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024 - Cochem, Germany
Duration: 19 Feb 202423 Feb 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14519 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024
Country/TerritoryGermany
CityCochem
Period19/02/2423/02/24

Keywords

  • 20F10
  • 68W30
  • complexity
  • Diophantine problem
  • finite groups
  • matrix groups
  • NP-completeness
  • spherical equations

Fingerprint

Dive into the research topics of 'Complexity of Spherical Equations in Finite Groups'. Together they form a unique fingerprint.

Cite this