Unbounded fan-in circuits and associative functions (Q1083202)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Unbounded fan-in circuits and associative functions |
scientific article |
Statements
Unbounded fan-in circuits and associative functions (English)
0 references
1985
0 references
The computation of finite semigroups using unbounded fan-in circuits is considered. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size \(O(nf^{-1}(n))\) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.
0 references
parallel computation
0 references
circuit complexity
0 references
computation of finite semigroups
0 references
semigroup product
0 references
primitive recursive function
0 references
0 references