The complexity of the realization of subdefinite matrices by gate schemes
type: Item
instance of: scholarly article
title: The complexity of the realization of subdefinite matrices by gate schemes
zbMATH Open document ID: 0641.94029
DOI: 10.1007/BF01159529
published in: Mathematical Notes
publication date: 1987-01-01T00:00:00Z
review text: 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)].
reviewed by: Indulis Strazdins
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4045651
zbMATH Keywords: asymptotic complexity
zbMATH Keywords: Boolean matrix
zbMATH Keywords: gate networks
author: Alexander E. Andreev
MaRDI profile type: Publication
cites work: Q3236503
description: scientific article; zbMATH DE number 4045651