On Negations in Boolean Networks

摘要

Although it is well known by a counting argument that relative to the full basis most Boolean functions need exponentially many operations, for explicit Boolean functions only linear lower bounds with small constant factors are known. For monotone networks (i.e., networks without negations) exponential lower bounds for explicit monotone Boolean functions have been proved. We describe the state of the art and give some arguments why techniques developed for the proof of lower bounds for monotone networks cannot easily be extended to Boolean networks with negations.