Quotient Structures and Groups Computable in Polynomial Time Full article
| Conference |
17th International Computer Science Symposium in Russia 29 Jun - 1 Jul 2022 , он-лайн |
||
|---|---|---|---|
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||
| Output data | Year: 2022, Volume: 13296 LNCS, Pages: 35-45 Pages count : 11 DOI: 10.1007/978-3-031-09574-0_3 | ||
| Tags | computable structures; groups; polynomial computability; primitive recursive structures | ||
| Authors |
|
||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
| 2 | Russian Foundation for Basic Research | 20-01-00300 |
Abstract:
We prove that every quotient structure of the form A/ E, where A is a structure computable in polynomial time (P -computable), and E is a P -computable congruence in A, is isomorphic to a P -computable structure. We also prove that for every P -computable group A= (A, · ), there is a P -computable group B≅ A, in which the inversion operation x- 1 is also P -computable. © 2022, Springer Nature Switzerland AG.
Cite:
Alaev P.
Quotient Structures and Groups Computable in Polynomial Time
Lecture Notes in Computer Science. 2022. V.13296 LNCS. P.35-45. DOI: 10.1007/978-3-031-09574-0_3 Scopus OpenAlex
Quotient Structures and Groups Computable in Polynomial Time
Lecture Notes in Computer Science. 2022. V.13296 LNCS. P.35-45. DOI: 10.1007/978-3-031-09574-0_3 Scopus OpenAlex
Identifiers:
| Scopus: | 2-s2.0-85134166548 |
| OpenAlex: | W4285261414 |