Multilevel representation and complexity of circuits of unbounded fan-in gates (Q2027864): Difference between revisions

Author's introduction: In this paper, we consider the complexity of the implementation of Boolean functions by circuits of functional elements over a basis of generalized conjunctions \(\{(x_1^{\alpha_1}\cdot\ldots\cdot x_k^{\alpha_k})^\beta \mid k\in\mathbb N; \alpha_i, \beta\in \{0, 1\}\}\) (Boolean degree is defined as \(x^1 = x\), \(x^0 = \bar x)\). By \(C_d(n)\) and \(C(n)\) we denote the complexity of functions of \(n\) variables (the Shannon function) when it is realized by circuits with depth \(d\) and circuits without depth restrictions over the indicated basis. The definitions of the circuit, the complexity and depth of the circuits, and the Shannon functions are standard and are given, for example, in [\textit{O. B. Lupanov}, Asymptotic complexity estimates of control systems (in Russian). Moscow: Izd. Mosk. Univ. (1984)] . The behavior of the Shannon function of circuit complexity over certain naturally defined infinite bases has been studied in a number of papers: the first tight results were obtained by \textit{A. A. Markov} [Dokl. Akad. Nauk SSSR 116, 917--919 (1957; Zbl 0079.24601)] and \textit{È. I. Nechiporuk} [Sov. Math., Dokl. 2, 1087--1088 (1961; Zbl 0115.12301); translation from Dokl. Akad. Nauk SSSR 139, 1302--1303 (1961)]. The asymptotics of \(\sqrt 2 \cdot 2^{n/2}\) for the complexity function of circuits over a basis of negations and free (i.e., with zero weight) disjunctions was established in Theorem 5 in [Nechiporuk, loc. cit.]. It is easy to check that this result is equivalent to the relation \(C(n) \sim \sqrt 2 \cdot 2^{n/2}\). The asymptotics \(C_3(n) \sim \cdot 2^{n/2}\), when implemented by circuits with depth of 3, was obtained in [the author, Discrete Math. Appl. 29, No. 4, 241--254 (2019; Zbl 1439.94116); translation from Diskretn. Mat. 30, No. 2, 120--137 (2018)]. The question of the asymptotics of \(C_d(n)\) for constant \(d\ge 4\) remains open. In this paper, the asymptotics of \(C(n)\) function is obtained by means of a transposition of the method published in [Nechiporuk, loc. cit.]. The point of departure is an idea of multilevel representation of functions, but the multilevel representation obtained in is not clearly expressed. An alternative method of proof and an explicit form of the multilevel representation of functions are proposed. Upper bounds in the form of \[ C_{d+O(1)}(n) \lesssim \sqrt{2d/(d-1)}\cdot 2^{n/2} \] are also calculated using the method.