On the complexity of realizing the powers of a Boolean \((n,n)\)-function (Q1345680)
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 732072
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of realizing the powers of a Boolean \((n,n)\)-function |
scientific article; zbMATH DE number 732072 |
Statements
On the complexity of realizing the powers of a Boolean \((n,n)\)-function (English)
0 references
13 August 1995
0 references
The studied problem of complexity is presented for circuits with functional elements in the basis \(\&\), \(\vee\), \(-\), the lengths of all chains of the circuits from input to output being equal. The complexity of a circuit \(S\) is the number \(L(S)\) of its gates and its depth \(T(S)\) is the total length of the chains from input to output. The basic result proved gives the complexity of the realization of the powers of the studied Boolean function and upper bounds for \(L(S)\) and \(T(S)\).
0 references
circuits
0 references
depth
0 references
complexity
0 references
Boolean function
0 references
upper bounds
0 references
0.8380138278007507
0 references
0.8370834589004517
0 references
0.8352028131484985
0 references
0.8344307541847229
0 references
