Lower bounds for the complexity of restrictions of Boolean functions (Q5954083)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1698509
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.9032433032989502
0 references
0.8941519856452942
0 references
0.8026822209358215
0 references
0.8004854917526245
0 references
