No label defined (Q3335688)

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 3867233
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3867233

      Statements

      0 references
      1984
      0 references
      combinational complexity
      0 references
      Monotone Boolean functions
      0 references
      Boolean networks
      0 references
      nonlinear lower bounds
      0 references
      monotone network complexity
      0 references
      Boolean convolution
      0 references
      generalized Boolean matrix product
      0 references
      [For the entire collection see Zbl 0538.00005.] Monotone Boolean functions may be computed in Boolean networks over the monotone basis \(\Omega_ m=\{\wedge,\vee \}\). For many explicitly defined functions \(f:\{0,1\}^ n\to \{0,1\}^ n\) one is able to prove nonlinear lower bounds on their monotone network complexity. Here the methods used for these bounds are discussed. An \(\Omega(n^{3/2})\)-bound for the Boolean convolution [J. Weiß: Eine \(n^{3/2}\)-untere Schranke für die Boolesche Konvolution. Diplomarbeit, Univ. Bielefeld (1982)] and the largest known bound, an \(\Omega(n^ 2\log^{-1}n)\)- bound for a generalized Boolean matrix product, are described in more detail.
      0 references

      Identifiers