Circuit complexity of symmetric Boolean functions in antichain basis

作     者：Podolskaya, Olga V. 

作者机构：Moscow MV Lomonosov State Univ Moscow 117234 Russia 

出 版 物：《DISCRETE MATHEMATICS AND APPLICATIONS》 (离散数学及应用)

年 卷 期：2016年第26卷第1期

页      面：31-39页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Boolean circuit complexity antichain functions Boolean circuits symmetric Boolean functions the Shannon function 

摘      要：We study the circuit complexity of Boolean functions in an infinite basis consisting of all characteristic functions of antichains over the Boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of n variables for all integers n 1 in this basis are [n+1/2] and [n/2] + 1 respectively. For the maximum circuit complexity of n-variable Boolean functions in this basis, we show that its order of growth is equal ton.