@inproceedings{b413da9296794487a917a1fcf39be4c4,
title = "Complexity of Spherical Equations in Finite Groups",
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.",
keywords = "20F10, 68W30, complexity, Diophantine problem, finite groups, matrix groups, NP-completeness, spherical equations",
author = "Caroline Mattes and Alexander Ushakov and Armin Wei{\ss}",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024 ; Conference date: 19-02-2024 Through 23-02-2024",
year = "2024",
doi = "10.1007/978-3-031-52113-3_27",
language = "English",
isbn = "9783031521126",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "383--397",
editor = "Henning Fernau and Serge Gaspers and Ralf Klasing",
booktitle = "SOFSEM 2024",
}