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
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
0 references
0.83992994
0 references
0.8369864
0 references
0.8360082
0 references
0.83200085
0 references
0.83094275
0 references
0.82757115
0 references
0.8251574
0 references
0.82493395
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