首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates
  • 本地全文:下载
  • 作者:Matthias Krause ; Pavel Pudlak
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:1994
  • 卷号:1994
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We investigate the computational power of depth two circuitsconsisting of MODr--gates at the bottom and a threshold gate atthe top (for short, threshold--MODr circuits) and circuits withtwo levels of MOD gates (MODp-MODq circuits.) In particular, wewill show the following results

    (i) For all prime numbers p and integers qr it holds thatif p divides r but not q then all threshold--MODq circuitsfor MODr have exponentially many nodes.

    (ii) For all integers r all problems computable by depth two ANDORNOT --circuits of (quasi) polynomial size can be represented by threshold--MODr circuits with (quasi)poly\-no\-mially many edges.

    (iii) There is a problem computable by depth three ANDORNOT --circuitsof linear size and constant bottom fan--in which for all r needsthreshold--MODr circuits with exponentially many nodes.

    (iv) For pr different primes, and q2 k positive integers,where p does not divide q every MODpk-MODq circuit for MODr has exponentially many nodes.

    Results (i) and (iii) imply the first known exponential lower bounds on thenumber of nodes of threshold--MODr circuits, r=2 .They are based on a new lower bound method for the representationlength of functions as threshold functions over predefinedfunction bases, which, in contrast to previous related techniquesworks even if theedge weights are allowed to be unbounded and if the bases are nonorthogonal.The special importance of result (iii) consists in the fact that the knownspectral--theoretically basedlower bound methods for threshold--XOR circuits can provablynot be applied toAC0--functions. Thus, by (ii), result (iii) is quite sharp and gives apartial (negative) answer to the(open) question whether there exist simulations of AC0--circuitsby small depth threshold circuits which are more efficient than thatgiven by Yao's important result that ACCTC03 [Y90].Finally we observe that our method works also forMODp-MODq circuits, if p is a power of a prime.

国家哲学社会科学文献中心版权所有