Reductions for monotone Boolean circuits

摘要

The large class, say NLOG, of Boolean functions, including 0-1 Sort and 0-1 Merge, have an upper bound of O(n log n) for their monotone circuit size, i.e., they have circuits with O(n log n) AND/OR gates of fan-in two. Suppose that we can use, besides such normal AND/OR gates, any number of more powerful "F-gates" which realize a monotone Boolean function F with r(≥ 2) inputs and r'(≥ 1) outputs. Note that the cost of each AND/OR gate is one and we assume that the cost of each F-gate is r. Now we define: A Boolean function/ in NLOG is said to be F-Easy if/ can be constructed by a circuit with AND/OR/F gates whose total cost is o(n log n). In this paper we show that 0-1 Merge is not F-Easy for an arbitrary monotone function F such that r' ≤ r/ log r.