The complexity of the parity function in unbounded fan-in, unbounded depth circuits (Q1183575)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The complexity of the parity function in unbounded fan-in, unbounded depth circuits |
scientific article; zbMATH DE number 33394
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of the parity function in unbounded fan-in, unbounded depth circuits |
scientific article; zbMATH DE number 33394 |
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
0 references
