Circuit complexity of slice functions and homogeneous functions

✍ Scribed by Shoichi Hirose; Shuzo Yajima

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 644 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690250603

✦ Synopsis

Abstract

This paper discusses the complexity from the viewpoint of the number of circuit elements for the slice functions and the homogeneous function, which belong to the class of monotonic logic functions. The slice function is one of those functions in which the circuit complexity is almost equal to the monotonic circuit complexity.

The n‐input k‐homogeneous function is considered as the first step, and it is shown that there exists a function with the k‐slice monotonic circuit complexity Ω(~n~C~k~/log~n~C~k~)and the monotonic circuit complexity of u(> k) slice is O(~n~log~n~). This property has already been shown by Wegener for the case of the k‐slice with the monotonic circuit complexity Ω(~n‐1~C~k‐1~/log~n‐1~C~k‐1~). The result in this paper is an improvement of his result, and is the optimal when k is a constant.

As the next step, a homogeneous function is shown where the monotonic circuit complexity is almost equal to the circuit complexity. As in the case of the slice function, if the lower bound ω(n(log__n__)^2^) for the monotonic circuit complexity for the n‐input homogeneous function is shown, the same lower bound is shown for the circuit complexity.