Computing Boolean functions by polynomials and threshold circuits

作     者：Krause, M Pudlák, P 

作者机构：Univ Mannheim D-68131 Mannheim Germany Acad Sci Czech Republic Inst Math CR-11567 Prague 1 Czech Republic 

出 版 物：《COMPUTATIONAL COMPLEXITY》 (计算复杂性)

年 卷 期：1998年第7卷第4期

页      面：346-370页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：complexity of Boolean functions threshold circuits circuit lower bounds representations by multivariate polynomials 

摘      要：We investigate the computational power of threshold-AND circuits versus threshold-XOR circuits. In contrast to the observation that, small weight threshold-AND circuits can be simulated by small weight threshold-XOR circuit, we present a function with small size unbounded weight threshold-AND circuits for which all threshold-XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold Rates cannot simulate alternation: There are AC(0,3)-functions which need exponential size threshold-AND circuits.