Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871)
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 4029460
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Lower bounds on the size of bounded depth circuits over a complete basis with logical addition |
scientific article; zbMATH DE number 4029460 |
Statements
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (English)
0 references
1987
0 references
Lower bounds for bounded depth circuits over \(\{\) \&,\(\vee,\oplus \}\) are given using a special structure of families of Boolean functions called regular models. The construction of bounded degree is described. These models are then used to deduce exponential lower bounds in the basis \(\{\) \&,\(\oplus \}\), and it is shown that they also hold in the basis \(\{\) \&,\(\vee,\oplus \}\).
0 references
circuit complexity of Boolean functions
0 references
bounded depth circuits
0 references
regular models
0 references
exponential lower bounds
0 references
0.8184471130371094
0 references
0.8149059414863586
0 references
0.8020143508911133
0 references
0.7989888191223145
0 references
