The Library
PIK MASSPRODUCTION AND AN OPTIMAL CIRCUIT FOR THE NECIPORUK SLICE
Tools
UNSPECIFIED. (1995) PIK MASSPRODUCTION AND AN OPTIMAL CIRCUIT FOR THE NECIPORUK SLICE. COMPUTATIONAL COMPLEXITY, 5 (2). pp. 132154. ISSN 10163328
Full text not available from this repository.Abstract
Let f : {0, 1}(n) > {0, 1}(m) be an moutput Boolean function in n variables. f is called a kslice if f(x) equals the allzero vector for all x with Hamming weight less than k and f(x) equals the allone vector for all x with Hamming weight more than k. Wegener showed that ''PIkset circuits'' (set circuits over prime implicants of length k) are at the heart of any optimum Boolean circuit for a kslice f. We prove that, in PIkset circuits, savings are possible for the mass production of any F\X, i.e., any collection F of m outputsets given any collection X of n inputsets, if their PIkset 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:  10163328  
Official Date:  1995  
Dates: 


Volume:  5  
Number:  2  
Number of Pages:  23  
Page Range:  pp. 132154  
Publication Status:  Published  
URI:  http://wrap.warwick.ac.uk/id/eprint/19215 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 