The Library
PIK MASS-PRODUCTION AND AN OPTIMAL CIRCUIT FOR THE NECIPORUK SLICE
Tools
UNSPECIFIED (1995) PIK MASS-PRODUCTION AND AN OPTIMAL CIRCUIT FOR THE NECIPORUK SLICE. COMPUTATIONAL COMPLEXITY, 5 (2). pp. 132-154. ISSN 1016-3328.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Let f : {0, 1}(n) --> {0, 1}(m) be an m-output Boolean function in n variables. f is called a k-slice if f(x) equals the all-zero vector for all x with Hamming weight less than k and f(x) equals the all-one vector for all x with Hamming weight more than k. Wegener showed that ''PIk-set circuits'' (set circuits over prime implicants of length k) are at the heart of any optimum Boolean circuit for a k-slice f. We prove that, in PIk-set circuits, savings are possible for the mass production of any F\X, i.e., any collection F of m output-sets given any collection X of n input-sets, if their PIk-set complexity satisfies SCm(F\X) greater than or equal to 3n + 2m. This PIk mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n + o(n) for the Neciporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity Theta(n(3/2)). Finally, the new circuit for the Neciporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | COMPUTATIONAL COMPLEXITY | ||||
Publisher: | BIRKHAUSER VERLAG AG | ||||
ISSN: | 1016-3328 | ||||
Official Date: | 1995 | ||||
Dates: |
|
||||
Volume: | 5 | ||||
Number: | 2 | ||||
Number of Pages: | 23 | ||||
Page Range: | pp. 132-154 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |