PublicationsManuscripts

On the number of NOT gates needed to invert n inputs

Yuval Filmus

We solve the following puzzle: given an arbitrary supply of AND gates and OR gates, invert $n$ inputs using as few NOT gates as possible.