A decomposition of Boolean functions (Q2708276)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A decomposition of Boolean functions |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A decomposition of Boolean functions |
scientific article |
Statements
A decomposition of Boolean functions (English)
0 references
13 September 2001
0 references
decompositions of Boolean functions
0 references
circuit complexity
0 references
The author considers certain decompositions of a Boolean function \(f\) in \(n\) variables into a given number \(s\) of partial functions, each of which agrees with \(f\) on some subset of a given size \(d\) of the \(n\)-cube. Conditions for the existence of such decompositions, as well as bounds for the various parameters involved, are presented. The circuit complexity of the function \(f\), measured over the basis of all two-place Boolean functions, plays a central role in these bounds.
0 references
