No label defined (Q3783567)
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 4047114
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4047114 |
Statements
1987
0 references
computational complexity
0 references
lower bounds
0 references
information flow
0 references
branching programs
0 references
Boolean functions
0 references
minimal programs
0 references
0.8000527024269104
0 references
0.7853116989135742
0 references
0.7656435370445251
0 references
0.7539363503456116
0 references
0.7534682750701904
0 references
[For the entire collection see Zbl 0633.00025.] Some observations on the effect of information flow to the width of branching programs are given. It is shown that almost all Boolean functions have minimal programs with a small information flow and, on the other hand, that for some concrete functions the information flow is rather complicated in all their minimal programs. For a related work see the author [Theor. Comput. Sci. 57, 113-129 (1988)].
0 references