A measure in which Boolean negation is exponentially powerful
Boolean functionscircuit sizecombinatorial complexitycomplexity measures for families of Boolean functionsformula sizeprojectionsrepresentation size
In this paper relations between several complexity measures for families of Boolean functions, such as circuit size, formula size, and (monotone) representation size are presented. Roughly speaking, the circuit size of a Boolean function f is the smallest circuit and its formula size is the smallest Boolean function representing f. Furthermore, a family P of functions is a sequence \(\{P_ n\}_{n\in S}\) where \(P_ n\) is a function of n variables and \(S\subseteq N\). A family P is (monotone) universal if all (monotone) functions f are (monotone) projections of some members of P. The (monotone) representation size with respect to a (monotone) universal family P for a (monotone) function f is defined to be the smallest m such that f is a (monotone) projection of \(P_ m\).
- Measure on Boolean algebras
- Measures on Boolean algebras
- Measures on Boolean Algebras
- Boolean powers and quantum measurements
- Boolean operations over measure algebras
- On various nonlinearity measures for Boolean functions
- scientific article; zbMATH DE number 7310064
- Bases of measurability in Boolean algebras
- A strong log-concavity property for measures on Boolean algebras
- scientific article; zbMATH DE number 1529761
This page was built for publication: A measure in which Boolean negation is exponentially powerful
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790083)
