Generic complexity of solving of equations in finite groups, semigroups and fields Full article
| Conference |
5th International Scientific and Technical Conference on Mechanical Science and Technology Update 16-17 Mar 2021 , Омск |
||||
|---|---|---|---|---|---|
| Journal |
Journal of Physics: Conference Series
ISSN: 1742-6588 , E-ISSN: 1742-6596 |
||||
| Output data | Year: 2021, Volume: 1901, Number: 1, Article number : 012047, Pages count : DOI: 10.1088/1742-6596/1901/1/012047 | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Russian Science Foundation | 18-71-10028 |
| 2 | Russian Science Foundation | 19-11-00209 |
Abstract:
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. © Published under licence by IOP Publishing Ltd.
Cite:
Rybalov A.
, Shevlyakov A.
Generic complexity of solving of equations in finite groups, semigroups and fields
Journal of Physics: Conference Series. 2021. V.1901. N1. 012047 . DOI: 10.1088/1742-6596/1901/1/012047 Scopus OpenAlex
Generic complexity of solving of equations in finite groups, semigroups and fields
Journal of Physics: Conference Series. 2021. V.1901. N1. 012047 . DOI: 10.1088/1742-6596/1901/1/012047 Scopus OpenAlex
Identifiers:
| Scopus: | 2-s2.0-85107332713 |
| OpenAlex: | W3165409693 |