On finding an estimate of the complexity of discrete k-valued functions

D.P. Dimitrichenko

---

Abstract: In this paper the concept of derivative and integral of discrete k-valued functions is introduced, taking into account the properties of the operations of addition and multiplication modulo k. Based on the property of completeness of the integral expansion of k-valued functions, a universal method is proposed for estimating the complexity of k-valued fully defined functions, including not having an analytical representation, but specified only in a tabular way, or representable using other tabular functions. The structure of the “primitive – derivative” relation is studied depending on the properties of the number k. A model in the form of a directed graph of this relationship is proposed. Three main types of introduced relations are identified.

Keywords: k-valued function, differentiation operator, integration operator, completeness property, integral basis functions, directed graph

For citation. Dimitrichenko D.P. On finding an estimate of the complexity of discrete k-valued functions. News of the Kabardino-Balkarian Scientific Center of RAS. 2023. No. 6(116). Pp. 142–151. DOI: 10.35330/1991-6639-2023-6-116-142-151

References

1. Gorbatov V.A. Fundamental’nyye osnovy diskretnoy matematiki [Fundamental foundations of discrete mathematics]. Moscow: Nauka, 2000. 544 p. (In Russian)
2. Panteleev V.I. Polynomial decomposition of K-valued functions by Differentiation and normalization operators. Izvestiya vysshikh uchebnykh zavedeniy: Matematika [News of higher educational institutions: Mathematics]. 1998. No. 1. Pp. 82–103. (In Russian)
3. Lyutikova L.A. Using a Boolean derivative to evaluate the significance of properties of recognized objects. E3S Web of Conferences 224. 01021 (2020).
4. Kostrykin A.I. Vvedeniye v algebru [Introduction to algebra]. Moskow: Nauka, 1977. 320 p. (In Russian)
5. Dimitrichenko D.P. On one way of differentiating logical functions. Materialy mezhdunarodnoy konferentsii molodykh uchenykh “Matematicheskoye modelirovaniye fraktal’nykh protsessov, rodstvennyye problemy analiza i informatiki” [Proceedings of the international conference of young scientists “Mathematical modeling of fractal processes, related problems of analysis and computer science”]. Nalchik, 2011. Pp. 103–105. (In Russian)
6. Dimitrichenko D.P. On the representation of a logical function through its derivatives. Materialy II mezhdunarodnogo rossiysko-uzbekskogo simpoziuma «Uravneniya smeshannogo tipa i smezhnyye problemy analiza i informatiki» [Materials of the II International Russian-Uzbek Symposium “Equations of mixed type and related problems of analysis and computer science”]. Nalchik, 2012. Pp. 92–94. (In Russian)

Information about the author

Dimitrichenko Dmitry Petrovich, Candidate of Technical Sciences, Senior Researcher of the Department of Neuroinformatics and Machine Learning, Institute of Applied Mathematics and Automation – branch of Kabardino-Balkarian Scientific Center of the Russian Academy of Sciences;
360000, Russia, Nalchik, 89 A Shortanov street;
dimdp@rambler.ru, ORCID: https://orcid.org/0000-0003-2399-3538