Alain P. Hiltgen and M.S. Paterson, PIk Mass Production and an Optimal Circuit for the Nechiporuk Slice (June 1, 1993).
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.
<%@ include file="cited.html" %>A.P. Hiltgen and M.S. Paterson, "PIk Mass Production and an Optimal Circuit for the Nechiporuk Slice", Computational Complexity 5(2), pp. 132-154 (1995)
<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>