首页 | 本学科首页   官方微博 | 高级检索  
     


Majority gates vs. general weighted threshold gates
Authors:Mikael Goldmann  Johan Håstad  Alexander Razborov
Affiliation:1. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44, Stockholm, SWEDEN
2. Steklov Mathematical Institute, Vavilova, 42, 117966, GSP-1, Moscow, RUSSIA
Abstract:In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following:
1.  A single threshold gate with weights cannot in general be replaced by a polynomial fan-in unweighted threshold gate of parity gates.
2.  On the other hand it can be replaced by a depth 2 unweighted threshold circuit of polynomial size. An extension of this construction is used to prove that whatever can be computed by a depthd polynomial size threshold circuit with weights can be computed by a depthd+1 polynomial size unweighted threshold circuit, whered is an arbitrary fixed integer.
3.  A polynomial fan-in threshold gate (with weights) of parity gates cannot in general be replaced by a depth 2 unweighted threshold circuit of polynomial size.
Keywords:circuit complexity  majority circuits  threshold circuits  lower bounds
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号