Name
Abstract | ||
|---|---|---|
In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting ''1'' over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e=O(n/l) and fan-in l, and then provide an almost tight lower bound e=@?(n-m"f)/l@? where m"f is the maximum numbers of consecutive ''0''s or ''1''s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2012.11.039 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Boolean function,fan-in l,complexity measure,n variable,energy e,combinatorial circuit,maximum number,logic circuit,value vector,symmetric Boolean function | Journal | 505, |
ISSN | Citations | PageRank |
0304-3975 | 2 | 0.40 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akira Suzuki | 1 | 51 | 8.44 |
| Kei Uchizawa | 2 | 74 | 12.89 |
| Xiao Zhou | 3 | 325 | 43.69 |