For a Boolean function f:{0,1}n→{0,1}$f:\{0,1{\}}^n\to \{0,1\}$ computed by a circuit C over a finite basis B$\mathcal{B}$, the energy complexity of C (denoted by ECB(C)${\mathsf{E}\mathsf{C}}_{\mathcal{B}}(C)$) is the maximum over all inputs {0,1}n$\{0,1{\}}^n$ the numbers of gates of the circuit C (excluding the inputs) that output a one. Energy complexity of a Boolean function over a finite basis B$\mathcal{B}$ denoted by Open image in new window

where C is a circuit over B$\mathcal{B}$ computing f.

We study the case when B={∧2,∨2,¬}$\mathcal{B}=\{{\wedge }_2,{\vee }_2,\mathrm{\neg }\}$, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most 3n(1+ϵ(n))$3n(1+ϵ(n))$ for a small ϵ(n)$ϵ(n)$(which we observe is improvable to 3n−1$3n-1$). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions.

For all Boolean functions f, EC(f)≤O(DT(f)3)$\mathsf{E}\mathsf{C}(f)\le O(\mathsf{D}\mathsf{T}(f{)}^3)$ where DT(f)$\mathsf{D}\mathsf{T}(f)$ is the optimal decision tree depth of f.

We define a parameter positive sensitivity (denoted by psens$\mathsf{p}\mathsf{s}\mathsf{e}\mathsf{n}\mathsf{s}$), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, EC(C)≥psens(f)/3$\mathsf{E}\mathsf{C}(C)\ge \mathsf{p}\mathsf{s}\mathsf{e}\mathsf{n}\mathsf{s}(f)/3$.

Restricting the above notion of energy complexity to Boolean formulas, denoted ECF(f)$\mathsf{E}{\mathsf{C}}^{\mathsf{F}}(f)$, we show that ECF(f)=Θ(L(f))$\mathsf{E}{\mathsf{C}}^{\mathsf{F}}(f)=\Theta (L(f))$ where L(f) is the minimum size of a formula computing f.

We next prove lower bounds on energy for explicit functions. In this direction, we show that for the perfect matching function on an input graph of n edges, any Boolean circuit with bounded fan-in must have energy Ω(n−−√)$\Omega (\sqrt{n})$. We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is Ω(n)$\Omega (n)$.