A measure in which Boolean negation is exponentially powerful (Q790083)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A measure in which Boolean negation is exponentially powerful |
scientific article |
Statements
A measure in which Boolean negation is exponentially powerful (English)
0 references
1983
0 references
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\).
0 references
combinatorial complexity
0 references
Boolean functions
0 references
complexity measures for families of Boolean functions
0 references
circuit size
0 references
formula size
0 references
representation size
0 references
projections
0 references