No label defined (Q3221885)
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 3889430
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3889430 |
Statements
1984
0 references
monotone computations
0 references
simulations
0 references
Boolean functions
0 references
slice functions
0 references
circuit complexity
0 references
Boolean convolution
0 references
clique functions
0 references
lower bounds
0 references
0.9117798805236816
0 references
0.8734368681907654
0 references
0.8580413460731506
0 references
0.853912889957428
0 references
0.8116021156311035
0 references
[For the entire collection see Zbl 0544.00022.] For an important subclass of all Boolean functions - the so called slice functions - the circuit complexity over complete bases or the monotone basis are nearly of the same size since pseudo complements can be computed efficiently. Here the complexity of pseudo complements and the complexity of some slices of important functions like Boolean convolution and clique functions are investigated. Furthermore some new models are introduced which lead to new possibilities of proving lower bounds on the circuit complexity of Boolean functions.
0 references