PI k mass production and an optimal circuit for the Ne?iporuk slice
| Autor: | Mike Paterson, Alain P. Hiltgen |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Discrete mathematics
Conjecture General Mathematics Boolean circuit Monotonic function Theoretical Computer Science Combinatorics Set (abstract data type) Computational Mathematics Asymptotically optimal algorithm Monotone polygon Computational Theory and Mathematics Production (computer science) Boolean function Mathematics |
| Zdroj: | Computational Complexity. 5:132-154 |
| ISSN: | 1420-8954 1016-3328 |
| DOI: | 10.1007/bf01268142 |
| Popis: | Let D: {0,1}n $ {0, 1}m be an m-output Boolean function in n variables. The k-slice of D is the monotone function Dsl-k defined component-wise by D (i)sl-k = (D (i) [ Tn k ) Z Tn k +1 , where Tnk is the kth threshold function. Wegener showed that certain ''PIk - set circuits'' are at the heart of any optimum Boolean circuit for a k-slice D. We prove that, in PIk - set circuits, savings are possible for the mass production of any F l X, i.e., any collection F of ms output-sets given any collection X of ns input-sets, if their PIk - set complexity satisfies SCm (F lX) 3 3ns + 2ms. This PIk mass production, which can be used also in monotone circuits for slice functions, is exploited then in different ways to obtain a monotone circuit of complexity 3n + o(n) for the canonical slice of the Nechiporuk sums, thus disproving a conjecture by Wegener that this slice has monotone complexity O(n3/2). Finally, we prove that this new circuit for the Nechiporuk slice is asymptotically optimal, not only with respect to monotone, but also with respect to combinational, complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink