Energy Complexity and Depth of Threshold Circuits
Kei Uchizawa, Takao Nishizeki and Eiji Takimoto
Abstract
In the paper we show that there is a close relationship between the
energy complexity and the depth of threshold circuits computing any
Boolean function although they have completely different physical
meanings. Suppose that a Boolean function f can be computed by a
threshold circuit C of energy complexity e and hence at most e threshold
gates in C output "1" for any input to C. We then prove that the
function f can be computed also by a threshold circuit C' of depth 2e+1
and hence the parallel computation time of C' is 2e+1. If the size of
C is s, that is, there are s threshold gates in C, then the size s' of
C' is s'=2es+1. Thus, if the size s of C is polynomial in the number n
of input variables, then the size s' of C' is polynomial in n, too.