On Saving Energy in Boolean Circuits via Negations
摘要
For a Boolean circuit C, the energy complexity of C is defined as the number of gates outputting ones in C, where the maximum is taken over all the input assignments. The energy complexity has been well-studied among various bases since 1960s. Monotone circuits incur high energy in terms of their size. In order to understand how much energy can be saved by using negations in the circuit design, in this paper, we study the contrast between two infinite bases \(\mathcal {B}_*\) and \(\mathcal {N}_*\) , where \(\mathcal {B}_*\) contains the conjunction of unbounded fan-in and disjunction of unbounded fan-in, and the negation, while \(\mathcal {N}_*\) contains the conjunction and disjunction with unbounded fan-in, where any input can be negated. Thus, a \(\mathcal {B}_*\) -circuit needs a single gate for negation, while \(\mathcal {N}_*\) -circuit can freely use negation without contributing to the energy of the circuit. We show that this “free” use of negations has a considerable impact on computational power of energy-bounded circuits, as follows: The results above show equipping gates with negations are helpful for energy-bounded circuits. On the limitation of \(\mathcal {N}_*\) -circuits, we show: