The complexity of the realization of subdefinite matrices by gate schemes (Q1101066)

Let \({\mathcal F}^*(p,q,\alpha)\) be the class of incompletely specified Boolean (p,q)-tables with \(\alpha\) pq defined elements, \(L^{(2)}(T)\) the complexity of the realization of the Boolean table (matrix) T by gate networks of depth 2. The author proves the asymptotic formula \(L^{(2)}({\mathcal F}^*(p,q,\alpha))\sim \alpha pq/\log \alpha p\) under the conditions \(p\geq q\), \(\alpha\) \(p\to \infty\), \(\alpha q/\log \alpha p\to \infty.\) Thus a final solution is obtained to the problem solved partially by \textit{O. B. Lupanov} [Dokl. Akad. Nauk SSSR 111, 1171-1174 (1956; Zbl 0072.432)] and \textit{Eh. I. Nechiporuk} [ibid. 163, 40-42 (1965; Zbl 0139.117)].