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

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

      Identifiers