Monotone circuit complexity

ID: monotone-circuit-complexity

Monotone circuit complexity studies Boolean circuits built only from AND and OR gates, without negations. Such circuits compute monotone Boolean functions, but some monotone functions require much larger monotone circuits than unrestricted circuits.

New to topics? Read the docs here!