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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    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