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 等数据库收录! |
|