On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials
In this paper, we examined the computational complexity of systems of monomials for some models that allow multiple use of intermediate results, such as composition circuits and multiplication circuits. For these models, we studied Shannon-type functions that characterize the maximum computationa...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2020-09-01
|
| Series: | Учёные записки Казанского университета. Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2020-3-5.html |
| _version_ | 1797965650861228032 |
|---|---|
| author | S.A. Korneev |
| author_facet | S.A. Korneev |
| author_sort | S.A. Korneev |
| collection | DOAJ |
| description | In this paper, we examined the computational complexity of systems of monomials for some models that allow multiple use of intermediate results, such as composition circuits and multiplication circuits.
For these models, we studied Shannon-type functions that characterize the maximum computational complexity of systems of monomials with exponents not exceeding the corresponding elements of a given matrix A. We found that for composition circuits, under the condition of unlimited growth of the maximum of matrix elements, this function grows asymptotically as the binary logarithm of the maximum absolute value (without regard to the sign) of the term from the determinant of the matrix A. Using generalized circuits as an auxiliary model, we transferred this result (under some restrictions) to the model of multiplication circuits. |
| first_indexed | 2024-04-11T02:03:22Z |
| format | Article |
| id | doaj.art-ce70215b9e24467495b69817506f7576 |
| institution | Directory Open Access Journal |
| issn | 2541-7746 2500-2198 |
| language | English |
| last_indexed | 2024-04-11T02:03:22Z |
| publishDate | 2020-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета. Серия Физико-математические науки |
| spelling | doaj.art-ce70215b9e24467495b69817506f75762023-01-03T03:40:08ZengKazan Federal UniversityУчёные записки Казанского университета. Серия Физико-математические науки2541-77462500-21982020-09-01162330031010.26907/2541-7746.2020.3.300-310On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomialsS.A. Korneev0Lomonosov Moscow State University, Moscow, 119991 Russia; Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Moscow, 125047 Russia In this paper, we examined the computational complexity of systems of monomials for some models that allow multiple use of intermediate results, such as composition circuits and multiplication circuits. For these models, we studied Shannon-type functions that characterize the maximum computational complexity of systems of monomials with exponents not exceeding the corresponding elements of a given matrix A. We found that for composition circuits, under the condition of unlimited growth of the maximum of matrix elements, this function grows asymptotically as the binary logarithm of the maximum absolute value (without regard to the sign) of the term from the determinant of the matrix A. Using generalized circuits as an auxiliary model, we transferred this result (under some restrictions) to the model of multiplication circuits.https://kpfu.ru/uz-eng-phm-2020-3-5.htmlset of monomialscomputation complexitycircuit complexityshannon function |
| spellingShingle | S.A. Korneev On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials Учёные записки Казанского университета. Серия Физико-математические науки set of monomials computation complexity circuit complexity shannon function |
| title | On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials |
| title_full | On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials |
| title_fullStr | On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials |
| title_full_unstemmed | On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials |
| title_short | On the asymptotic behavior of Shannon-type functions characterizing the computing complexity of systems of monomials |
| title_sort | on the asymptotic behavior of shannon type functions characterizing the computing complexity of systems of monomials |
| topic | set of monomials computation complexity circuit complexity shannon function |
| url | https://kpfu.ru/uz-eng-phm-2020-3-5.html |
| work_keys_str_mv | AT sakorneev ontheasymptoticbehaviorofshannontypefunctionscharacterizingthecomputingcomplexityofsystemsofmonomials |