Parity, circuits, and the polynomial-time hierarchy (Q3318683)

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 3849129
Language Label Description Also known as
default for all languages
No label defined
    English
    Parity, circuits, and the polynomial-time hierarchy
    scientific article; zbMATH DE number 3849129

      Statements

      Parity, circuits, and the polynomial-time hierarchy (English)
      0 references
      0 references
      0 references
      0 references
      1984
      0 references
      Boolean circuits
      0 references
      lower bound
      0 references
      parity function
      0 references
      multiplication
      0 references
      transitive closure
      0 references
      polynomial-time hierarchy
      0 references
      The authors investigate lower bounds on the size of Boolean circuits computing parity, multiplication and transitive closure. It is already known [\textit{O. B. Lupanov}, Probl. Kibern. 6, 5--14 (1961; Zbl 0178.33104)] that Boolean circuits of depth 2 computing the parity function must have an exponential number of gates (in the number of the variables). The authors investigate the more general case of constant depth and show, that the number of gates for the computation of the parity function cannot be polynomial. By reduction it is shown, that also some other problems are not computable by polynomial-size constant-depth circuits. For this purpose the authors define: f is constant-depth polynomial-size reducible to g (\(f\leq_{cp}g)\) if f can be realized with constant-depth polynomial-size circuits on literals, made up of \(\wedge\), \(\vee\), - gates and gates computing g. It is shown, that parity can be \(\leq_{cp}\)-reduced to multiplication and to the transitive closure problem for Boolean matrices; thus multiplication and transitive closure are not computable by constant-depth polynomial-size circuits. Furthermore the authors give an application to the polynomial time hierarchy PH \((PH^ A:\) the hierarchy relativized by the oracle A); using the complexity of the parity function, they show that there is an oracle A such that \(PSPACE^ A-PH^ A\neq \emptyset\).
      0 references

      Identifiers