The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields
An approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced. The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of n-ary functio...
| 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-4.html |
| _version_ | 1797970816809304064 |
|---|---|
| author | A.S. Baliuk |
| author_facet | A.S. Baliuk |
| author_sort | A.S. Baliuk |
| collection | DOAJ |
| description | An approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced.
The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of n-ary functions over an arbitrary finite field Fq. The value found is equal to qn−1. The previously known result for Boolean functions was generalized. |
| first_indexed | 2024-04-11T03:21:51Z |
| format | Article |
| id | doaj.art-c9c7c90e913240f3bc46b65c7ce36359 |
| institution | Directory Open Access Journal |
| issn | 2541-7746 2500-2198 |
| language | English |
| last_indexed | 2024-04-11T03:21:51Z |
| publishDate | 2020-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета. Серия Физико-математические науки |
| spelling | doaj.art-c9c7c90e913240f3bc46b65c7ce363592023-01-02T08:42:32ZengKazan Federal UniversityУчёные записки Казанского университета. Серия Физико-математические науки2541-77462500-21982020-09-01162328529910.26907/2541-7746.2020.3.285-299The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fieldsA.S. Baliuk0Irkutsk State University, Irkutsk, 664003 RussiaAn approach enabling partial generalization of the Green–Sasao hierarchy for polynomial forms of Boolean functions to the case of an arbitrary finite field was introduced. The exact value of the Shannon function was obtained for the class of pseudo-Kroneker and free-Kronecker forms of n-ary functions over an arbitrary finite field Fq. The value found is equal to qn−1. The previously known result for Boolean functions was generalized.https://kpfu.ru/uz-eng-phm-2020-3-4.htmlfinite fieldcomputational complexityfree-kronecker formspseudo-kronecker forms |
| spellingShingle | A.S. Baliuk The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields Учёные записки Казанского университета. Серия Физико-математические науки finite field computational complexity free-kronecker forms pseudo-kronecker forms |
| title | The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields |
| title_full | The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields |
| title_fullStr | The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields |
| title_full_unstemmed | The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields |
| title_short | The complexity of pseudo-Kronecker and free-Kronecker forms of functions over finite fields |
| title_sort | complexity of pseudo kronecker and free kronecker forms of functions over finite fields |
| topic | finite field computational complexity free-kronecker forms pseudo-kronecker forms |
| url | https://kpfu.ru/uz-eng-phm-2020-3-4.html |
| work_keys_str_mv | AT asbaliuk thecomplexityofpseudokroneckerandfreekroneckerformsoffunctionsoverfinitefields AT asbaliuk complexityofpseudokroneckerandfreekroneckerformsoffunctionsoverfinitefields |