Open AccessGeneric complexity of solving of equations in finite groups, semigroups and fields
Author(s) -
Alexander Rybalov,
Artem N. Shevlyakov
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1901/1/012047
Subject(s) - finite field , foundation (evidence) , mathematics , algebra over a field , polynomial , computer science , discrete mathematics , pure mathematics , mathematical analysis , political science , law
The paper is devoted by investigation of generic complexity of the algorithmic problem of solving of systems of equations in finite groups, finite semigroups and finite fields. We show that if this problem is intractable in the worst case and P = BPP, then there is no polynomial strongly generic algorithm, which solves it. The first author is supported by Russian Science Foundation, grant 19-11-00209. The second author is supported by Russian Science Foundation, grant 18-71-10028.