Nearly optimal hierarchies for network and formula size (Q1061717)
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: Nearly optimal hierarchies for network and formula size |
scientific article; zbMATH DE number 3910304
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Nearly optimal hierarchies for network and formula size |
scientific article; zbMATH DE number 3910304 |
Statements
Nearly optimal hierarchies for network and formula size (English)
0 references
1986
0 references
How large are the ''gaps'' in the complexity hierarchies for Boolean functions with respect to network size and formula size? A gap is a non- empty interval of integers none of which is the complexity of any Boolean function. It is shown for the most natural bases that there are no gaps at all over a broad range of values and that the largest gap anywhere is less than n.
0 references
gaps
0 references
complexity hierarchies for Boolean functions
0 references
network size
0 references
formula size
0 references
