Lower bounds for the complexity of restrictions of Boolean functions (Q5954083)
From MaRDI portal
scientific article; zbMATH DE number 1698509
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds for the complexity of restrictions of Boolean functions |
scientific article; zbMATH DE number 1698509 |
Statements
Lower bounds for the complexity of restrictions of Boolean functions (English)
0 references
14 February 2003
0 references
Given a Boolean function \(f\) and a set \(M\) of domains, the circuit size complexity of the most complicated restriction of \(f\) to some domain in \(M\) is studied. Upper and lower bounds, depending on the domain size, are established for wide classes of Boolean functions. Similar results for other complexity measures (e.g., formula size) are given.
0 references
Boolean function
0 references
circuit size complexity
0 references