The complexity of the parity function in unbounded fan-in, unbounded depth circuits (Q1183575): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q208754 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Juraj Hromkovič / rank | |||
Normal rank | |||
Revision as of 04:08, 11 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of the parity function in unbounded fan-in, unbounded depth circuits |
scientific article |
Statements
The complexity of the parity function in unbounded fan-in, unbounded depth circuits (English)
0 references
28 June 1992
0 references
An involved study of the complexity of the parity function \(f_ n\) of \(n\) variables realised by unbounded fan-in Boolean circuits is presented. The number of gates of a circuit is considered as the main complexity measure, but the number of wires is also investigated in some cases. Several optimal and almost optimal (lower and upper) bounds on the complexity of \(f_ n\) for distinct bases are established. The proof techniques used include several nice ideas, and are interesting for everybody working in Boolean function complexity theory.
0 references
complexity of the parity function
0 references
unbounded fan-in Boolean circuits
0 references
complexity measure
0 references
Boolean function complexity theory
0 references
